配点 : $400$ 点

問題文

$N = 2^{20}$ 項からなる数列 $A = (A_0, A_1, \dots, A_{N - 1})$ があります。はじめ、全ての要素は $-1$ です。

$Q$ 個のクエリを順番に処理してください。$i \, (1 \leq i \leq Q)$ 個目のクエリは $t_i = 1$ または $t_i = 2$ を満たす整数 $t_i$ および整数 $x_i$ で表され、内容は以下の通りです。

• $t_i = 1$ のとき、以下の処理を順番に行う。1. 整数 $h$ を $h = x_i$ で定める。 2. $A_{h \bmod N} \neq -1$ である間、$h$ の値を $1$ 増やすことを繰り返す。この問題の制約下でこの操作が有限回で終了することは証明できる。 3. $A_{h \bmod N}$ の値を $x_i$ で書き換える。
• $t_i = 2$ のとき、その時点での $A_{x_i \bmod N}$ の値を出力する。

なお、整数 $a, b$ に対し、$a$ を $b$ で割った余りを $a \bmod 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)$
• $t_i = 2$ であるような $i \, (1 \leq i \leq Q)$ が $1$ つ以上存在する。
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$Q$

$t_1$ $x_1$

$\vdots$

$t_{Q}$ $x_{Q}$

出力

$t_i = 2$ であるようなクエリに対し、それぞれ答えを $1$ 行に出力せよ。そのようなクエリが $1$ つ以上存在することは保証される。

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$ は定数であり、入力では与えられないことに注意してください。