問題文

長さ N の整数列 \{A_n\} が与えられます。以下の Q 個のクエリを順に処理してください。

• T_i=1 のとき: 数列の第 x 項 (=A_x) の値と第 y 項 (=A_y) の値を入れ替える。
• T_i=2 のとき: 数列を右方向にシフトする。すなわち、\{A_n\} = A_N, A_1, A_2, \cdots, A_{N-1} とする。
• T_i=3 のとき: 数列の第 x 項 (=A_x) の値を求める。

制約

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_n \leq 10^9 (1 \leq n \leq N)
• 1 \leq T_i \leq 3 (1 \leq i \leq Q)
• T_i = 1 ならば 1 \leq x_i, y_i \leq N かつ x_i \neq y_i
• T_i = 2 ならば x_i=y_i=0
• T_i = 3 ならば 1 \leq x_i \leq N かつ y_i=0
• 入力中の値はすべて整数である

入力例 1

8 5
6 17 2 4 17 19 1 7
2 0 0
1 7 2
1 2 6
1 4 5
3 4 0

出力例 1

4

最初、数列は 6, 17, 2, 4, 17, 19, 1, 7 です。
1 番目のクエリでは、数列を右方向にシフトします。この操作のあと、数列は 7, 6, 17, 2, 4, 17, 19, 1 となります。
2 番目のクエリでは、数列の第 7 項と第 2 項を入れ替えます。この操作のあと、数列は 7, 19, 17, 2, 4, 17, 6, 1 となります。
3 番目のクエリでは、数列の第 2 項と第 6 項を入れ替えます。この操作のあと、数列は 7, 17, 17, 2, 4, 19, 6, 1 となります。
4 番目のクエリでは、数列の第 4 項と第 5 項を入れ替えます。この操作のあと、数列は 7, 17, 17, 4, 2, 19, 6, 1 となります。
5 番目のクエリでは、数列の第 4 項の値 A_4=4 を出力します。

入力例 2

9 6
16 7 10 2 9 18 15 20 5
2 0 0
1 1 4
2 0 0
1 8 5
2 0 0
3 6 0

出力例 2

18

最初、数列は 16, 7, 10, 2, 9, 18, 15, 20, 5 です。
1 番目のクエリのあと、数列は 5, 16, 7, 10, 2, 9, 18, 15, 20 となります。
2 番目のクエリのあと、数列は 10, 16, 7, 5, 2, 9, 18, 15, 20 となります。
3 番目のクエリのあと、数列は 20, 10, 16, 7, 5, 2, 9, 18, 15 となります。
4 番目のクエリのあと、数列は 20, 10, 16, 7, 18, 2, 9, 5, 15 となります。
5 番目のクエリのあと、数列は 15, 20, 10, 16, 7, 18, 2, 9, 5 となります。
6 番目のクエリでは、数列の第 6 項の値 A_6=18 を出力します。

入力例 3

11 18
23 92 85 34 21 63 12 9 81 44 96
3 10 0
3 5 0
1 3 4
2 0 0
1 4 11
3 11 0
1 3 5
2 0 0
2 0 0
3 9 0
2 0 0
3 6 0
3 10 0
1 6 11
2 0 0
3 10 0
3 4 0
3 5 0

出力例 3

44
21
34
63
85
63
21
34
96