题目描述

维护一个长度为 $2^{20}$ 的，下标从 $0$ 到 $2^{20}-1$ 的数列 $a$。初始时，数列中的每一项均为 $-1$。令 $n=2^{20}$。

给定 $q$ 次操作，每次操作内容如下：

• 1 x：将变量 $h$ 的值定为 $x$。将 $h$ 不断加 $1$ 直到 $a_{h \bmod n} = -1$ 为止。令 $a_{h \bmod n}$ 的值为 $x$。
• 2 x：输出 $a_{x \bmod n}$ 的值。

输入格式

第一行输入一个整数 $q$

接下来 $q$ 行每行两个整数 $op,x$，其中 $op\in(1,2)$

输出格式

输出若干行，对于每个询问 $2$ 回答一个答案。

4
1 1048577
1 1
2 2097153
2 3

1048577
-1

提示

• $1 \le q \le 2 \times 10^5$，$0 \le x_i \le 10^{18}$；
• 至少存在一个形如2 x的操作；
• 输入均为整数。

Sample Explanation 1

我们有 $x_1 \bmod N = 1$ ，因此第一个查询设置为 $A _1 = 1048577$ 。

在第二个查询中，最初我们有 $h = x_2$ ，其中有 $A_{h \bmod N} = A_{1} \neq -1$ ，因此我们在 $h$ 中添加 $1$ 。现在我们有 $A_{h \bmod N} = A_{2} = -1$ ，因此该查询设置了 $A_2 = 1$ 。

在第三个查询中，我们打印 $A_{x_3 \bmod N} = A_{1} = 1048577$ 。

在第四个查询中，我们打印 $A_{x_4 \bmod N} = A_{3} = -1$ 。

请注意，在这个问题中， $N = 2^{20} = 1048576$ 是一个常量，并没有在输入中给出。