配点: 3 点
問題文
长度 小于或等于 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
- 所有输入值均为整数 按给定顺序输出查询
入力
输入是按以下格式从标准输入给出的。
N Q A_1 A_2 \cdots A_N T_1 x_1 y_1 \vdots T_Q x_Q y_Q
出力
T_i=3 的答案,并以换行符分隔。
入力例 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 。
第一个查询将数字序列向右移动。经过此操作后,数列变为 7, 6, 17, 2, 4, 17, 19, 1 。
对于
在第二个查询中,数字 7 节与节 2 交换条款。经过此操作后,数列变为 7, 19, 17, 2, 4, 17, 6, 1 。
对于
在第三个查询中,数字 2 节与节 6 交换条款。经过此操作后,数列变为 7, 17, 17, 2, 4, 19, 6, 1 。
对于
在第四个查询中,数字 4 节与节 5 交换条款。经过此操作后,数列变为 7, 17, 17, 4, 2, 19, 6, 1 。
对于
在第五个查询中,数字 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 。
第一次查询后,编号顺序为 5, 16, 7, 10, 2, 9, 18, 15, 20 。
对于
第二次查询后,编号顺序为 10, 16, 7, 5, 2, 9, 18, 15, 20 。
对于
第三次查询后,编号顺序为 20, 10, 16, 7, 5, 2, 9, 18, 15 。
对于
第四次查询后,编号顺序为 20, 10, 16, 7, 18, 2, 9, 5, 15 。
对于
第五次查询后,序列为 15, 20, 10, 16, 7, 18, 2, 9, 5 。
对于
在第六个查询中,数量 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