线性探测

题目描述

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

请按顺序处理 $Q$ 个查询。第 $i$ 个查询（$1 \le i \le Q$）由满足 $t_i = 1$ 或 $t_i = 2$ 的整数 $t_i$ 以及整数 $x_i$ 表示，内容如下：

当 $t_i = 1$ 时，按顺序执行以下处理。

• 用 $h = x_i$ 定义整数 $h$。
• 当 $A_{h \bmod N} \neq -1$ 时，不断将 $h$ 的值加 $1$。可以证明，在本问题的约束下，该操作在有限次内结束。
• 将 $A_{h \bmod N}$ 的值改写为 $x_i$。

当 $t_i = 2$ 时，输出此时 $A_{x_i \bmod N}$ 的值。

另外，对于整数 $a, b$，$a$ 除以 $b$ 的余数记作 $a \bmod b$。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

对每个满足 $t_i = 2$ 的查询，将答案各输出一行。保证至少存在一个这样的查询。

样例

4
1 1048577
1 1
2 2097153
2 3

1048577
-1

因为 $x_1 \bmod N = 1$，所以第 $1$ 个查询使 $A_1 = 1048577$。

在第 $2$ 个查询中，初始 $h = x_2$，此时 $A_{h \bmod N} = A_{1} \neq -1$，所以将 $h$ 的值加 $1$。此时 $A_{h \bmod N} = A_{2} = -1$，因此该查询使 $A_2 = 1$。

在第 $3$ 个查询中，输出 $A_{x_3 \bmod N} = A_{1} = 1048577$。

在第 $4$ 个查询中，输出 $A_{x_4 \bmod N} = A_{3} = -1$。

注意，在本问题中 $N = 2^{20} = 1048576$ 是常数，不会在输入中给出。

数据范围

• $1 \le Q \le 2 \times 10^5$
• $t_i \in \{ 1, 2 \} \, (1 \le i \le Q)$
• $0 \le x_i \le 10^{18} \, (1 \le i \le Q)$
• 至少存在一个 $i$（$1 \le i \le Q$）使得 $t_i = 2$
• 输入均为整数