問題文

空の列 $A$ が与えられます。

$Q$ 個のクエリが与えられるので、順番に処理してください。
クエリは次の $3$ 種類のいずれかです。

• 1 x : $A$ の最後尾に $x$ を追加する。
• 2 : $A$ の最初の要素を出力する。その後、その要素を削除する。このクエリが与えられるとき、$A$ は空でないことが保証される。
• 3 : $A$ を反転させる。

制約

• $1 \leq Q \leq 10^5$
• $0 \leq x \leq 10^9$
• クエリ 2 が与えられるとき、$A$ は空でない。
• 入力はすべて整数である。

入力

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

Q
query1
query2
...
queryQ

$i \: (1 \leq i \leq Q)$ 番目の query $i$ では、まずクエリの種類 $t_i$ $(1, 2, 3$ のいずれか$)$ が与えられ、$t_i = 1$ のときは追加で $x$ が与えられる。
すなわち、各クエリは以下に示す $3$ つの形式のいずれかが与えられる。

1 x

2

3

出力

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

入出力例

10
1 1
1 2
1 3
1 4
1 5
2
1 8
3
2
2

1
8
5

入力例 $1$ において、$i$ 番目のクエリを処理した後の $A$ の状態を $i$ 行目に示すと以下のようになります。

• $(1)$
• $(1, 2)$
• $(1, 2, 3)$
• $(1, 2, 3, 4)$
• $(1, 2, 3, 4, 5)$
• $(2, 3, 4, 5)$
• $(2, 3, 4, 5, 8)$
• $(8, 5, 4, 3, 2)$
• $(5, 4, 3, 2)$
• $(4, 3, 2)$

14
1 294
2
1 109
1 162
2
2
1 667
2
1 416
1 135
1 192
3
2
2

294
109
162
667
192
135