题目描述

$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$ と表します。

输入格式

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

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

输出格式

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

题目大意

题目描述

维护一个长度为 $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}$ 的值。

说明/提示

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

4
1 1048577
1 1
2 2097153
2 3

1048577
-1

提示

制約

• $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$ つ以上存在する。
• 入力は全て整数である。

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