問題文

あなたはカードを整理するために 1 つの山札を作ります。 最初、山札にカードは 1 枚もありません。

これから Q 個の操作を行います。i 番目 (1 \leq i \leq Q) の操作では以下を行います：

• t_i = 1 のとき、整数 x_i が書かれたカードを山札の一番上にいれる
• t_i = 2 のとき、整数 x_i が書かれたカードを山札の一番下にいれる
• t_i = 3 のとき、山札の上から x_i 番目のカードに書かれた数を紙に書き出す

t_i = 3 の操作で書き出された整数を操作順に出力するプログラムを書いてください。

制約

• 2 \leq Q \leq 10^5
• 1 \leq t_i \leq 3
• t_i = 1, 2 のとき 1 \leq x_i \leq 10^9
• t_i = 3 のとき 1 \leq x_i \leq k_i（k_i は 1 \leq j \leq i かつ t_j = 1, 2 を満たす j の個数）
• t_i = 1, 2 を満たす i が少なくとも 1 つ存在する
• t_i = 3 を満たす i が少なくとも 1 つ存在する
• 与えられる入力は全て整数

入力例 1

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

出力例 1

1
2
3

山札は各操作の後に次の状態になります。

• 1 番目の操作の直後：カードに書かれた整数は上から順に (2) である
• 2 番目の操作の直後：カードに書かれた整数は上から順に (1, 2) である
• 3 番目の操作以降：カードに書かれた整数は上から順に (1, 2, 3) である

したがって、書き出された数は順番に 1、2、3 となります。

入力例 2

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

出力例 2

1
1
1

カードを山札の一番下にいれる操作のみを行います。
最初、1 が書かれたカードを山札にいれるので、t_i = 3 で書き出す数は常に 1 となります。　

入力例 3

6
1 1000000000
2 200000000
1 30000000
2 4000000
1 500000
3 3

出力例 3

1000000000