F - Hotel Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

長さ 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} を出力する。

制約

  • 1 \leq Q \leq 2\times 10^5
  • 1\leq x\leq 10^{9}
  • 出力クエリが少なくとも1つ存在する
  • 入力はすべて整数

入力

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

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 番目のそのようなクエリに対する答えを出力せよ。

入力例 1

6
1 4
3 3
1 3
3 2
2 3
3 2

出力例 1

-1
4
3

クエリ 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)
となっています。

入力例 2

8
1 8
2 5
2 5
3 7
3 8
3 9
2 3
3 1

出力例 2

5
1
-1
3