题目描述

有一个由 $N = 2^{20}$ 个项构成的序列 $A = (A_0, A_1, \dots, A_{N - 1})$。初始时，每个项都是 $\-1$。

按顺序执行 $Q$ 个查询。第 $i$ 个查询（$1 \leq i \leq Q$）由整数 $t_i$ 和另一个整数 $x_i$ 描述如下：

• 如果 $t_i = 1$，按顺序执行以下操作。
  1. 将整数 $h$ 定义为 $h = x_i$。
  2. 当 $A_{h \bmod N} \neq -1$ 时，不断将 $h$ 增加 $1$。我们可以证明，在本问题的约束条件下，此过程会在有限次迭代之后结束。
  3. 用 $x_i$ 替换 $A_{h \bmod N}$ 的值。
• 如果 $t_i = 2$，则在此时打印出 $A_{x_i \bmod N}$ 的值。

这里，对于整数 $a$ 和 $b$，$a \bmod b$ 表示 $a$ 除以 $b$ 的余数。

约束条件

• $1 \leq Q \leq 2 \times 10^5$
• $t_i \in \{ 1, 2 \} \, (1 \leq i \leq Q)$
• $0 \leq x_i \leq 10^{18} \, (1 \leq i \leq Q)$
• 至少有一个 $i$ 满足 $t_i = 2$。
• 输入中的所有值都是整数。

输入

从标准输入获取以下格式的输入：

$Q$ $t_1$ $x_1$ $\vdots$ $t_{Q}$ $x_{Q}$

输出

对于每个满足 $t_i = 2$ 的查询，打印出一行响应。保证至少存在一个此类查询。

示例输入 1

4
1 1048577
1 1
2 2097153
2 3

示例输出 1

1048577
-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$ 是一个常数，不在输入中给出。