問題文

長さ N の配列 A = [A_1, \ldots, A_N] があり、最初はすべての i について A_i = i となっています。あなたは配列に対して Q 回の操作を行います。j 回目の操作は文字列 Query_j で表されます。

• 変更操作：Query_j = \ 1 x y のとき、A_x の値を y に変更する
• 反転操作：Query_j = \ 2 のとき、配列 A を逆順にする
• 取得操作：Query_j = \ 3 x のとき、A_x の値を答える

すべての取得操作に対して、正しく答えるプログラムを作成してください。

制約

• 1 \leq N \leq 200000
• 1 \leq Q \leq 200000
• どのタイミングでも、配列 A の要素は 1 以上 10^9 以下の整数である

入力例 1

5 4
1 4 8
3 2
2
3 2

出力例 1

2
8

配列 A は [1, 2, 3, 4, 5] \rightarrow [1, 2, 3, 8, 5] \rightarrow [5, 8, 3, 2, 1] と変化します。