問題文

$N$ 個の積み木が縦に積まれている。下から数えて$i(1 \leq i \leq N)$番目の積み木には数字$a_i$が書かれている。この積み木に対して、次の4種類のクエリから構成される $Q$ 個のクエリを処理せよ。

• クエリ$1$ : 一番上の積み木の上に新しく数字 $k$ と書かれた積み木を乗せる。
• クエリ$2$ : 下から $p$ 番目の積み木に書かれた数字を出力する。
• クエリ$3$ : 一番上の積み木を取り除き、その数字を出力する。
• クエリ$4$ : 積み木を上下逆さまにする。つまり、下から数えて$i(1 \leq i \leq K)$番目の積み木は上から数えて$i$番目の位置に移動する。

制約

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq a_i,k \leq 10^9$
• クエリ$3$を行う時点での積み木の個数は$1$個以上であることが保証される。
• クエリ$2,3$は$1$回以上与えられることが保証される。

入力

入力はすべて整数である。

N Q
a_1 a_2 ... a_N
Query_1
Query_2
...
Query_N

各クエリは以下のように与えられる。<br> クエリ$1$

1 K

クエリ$2$

2 p

クエリ$3$

3

クエリ$4$

4

出力

クエリ$2,3$の出力を各クエリごとに1行づつ出力せよ。

サンプル

2 2
1 3
4
2 1

3

クエリ$4$によって積み木が上下逆さまになっています。

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

4
1