AT_tupc2023_f Hotel

長さ $ 1 $ の整数列 $ A=(1) $ があります。 クエリが $ Q $ 個与えられるので順に処理してください。 クエリは以下の $ 3 $ 種類です。 いずれも、各クエリ処理前の数列 $ A $ の長さを $ n $ とし、 $ A=(a_{1},a_{2},\dots,a_{n}) $ とします。 - `1 x` : $ A $ を長さ $ n+1 $ の数列 $ (x,a_{1},a_{2},\dots,a_{n}) $ に置き換える。 - `2 x` : $ A $ を長さ $ 2n $ の数列 $ (x,a_{1},x,a_{2},\dots,x,a_{n}) $ に置き換える。 - `3 x` : $ x>n $ ならば $ -1 $ を出力する。 $ x\le n $ ならば $ a_{x} $ を出力する。

入力は以下の形式で標準入力から与えられる。 > $ Q $ $ t_1 $ $ x_1 $ $ t_2 $ $ x_2 $ $ \vdots $ $ t_Q $ $ x_Q $ ここで、 $ t_i $ $ (1\leq i\leq Q) $ はクエリの種類を表す整数で、 $ t_i=1,2,3 $ のいずれかである。

$ t_i=3 $ を満たすクエリの回数を $ q $ として、 $ q $ 行出力せよ。 $ j $ $ (1\leq j\leq q) $ 行目では、 $ j $ 番目のそのようなクエリに対する答えを出力せよ。

### Sample Explanation 1 クエリ $ 1 $ 前: $ A=(1) $ クエリ $ 1 $ 後: $ A=(4,1) $ クエリ $ 2 $ 後: $ A=(4,1) $ クエリ $ 3 $ 後: $ A=(3,4,1) $ クエリ $ 4 $ 後: $ A=(3,4,1) $ クエリ $ 5 $ 後: $ A=(3,3,3,4,3,1) $ クエリ $ 6 $ 後: $ A=(3,3,3,4,3,1) $ となっています。 ### Constraints - $ 1 \leq Q \leq 2\times 10^5 $ - $ 1\leq x\leq 10^{9} $ - 出力クエリが少なくとも1つ存在する - 入力はすべて整数