当前没有测试数据。

D - 线性探测

分数：$400$ 分

问题描述

有一个包含 $N = 2^{20}$ 个元素的序列 $A = (A_0, A_1, \dots, A_{N - 1})$。初始时，序列中的每个元素都为 $-1$。

按照顺序处理 $Q$ 个查询。第 $i$ 个查询 $(1 \leq i \leq Q)$ 包含一个整数 $t_i$ ($t_i = 1$ 或 $t_i = 2$) 和另一个整数 $x_i$。

• 如果 $t_i = 1$，按照以下步骤进行：
  1. 定义一个整数 $h$ 为 $h = x_i$。
  2. 当 $A_{h \bmod N} \neq -1$ 时，不断将 $1$ 加到 $h$ 上。根据该问题的约束条件，我们可以证明这个过程在有限次迭代后会结束。
  3. 将 $A_{h \bmod N}$ 的值替换为 $x_i$。
• 如果 $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$ 的查询，输出一个结果。

样例解释

对于第一个查询，$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$ 是一个常数，不会在输入中给出。