分数: 300 点
问题陈述
有一个整数序列 A 长度 N,最初 A_i = i。 总共处理了 Q 以下类型的查询:
- 类型 1:更改 A_p to x.
- 类型 2:输出 A_p.
- 类型 3: 重复操作“移动第一个元素 A 到最后” k 次。
- 正式地,替换 A 与 (A_2,A_3,\dots,A_N,A_1) k 次。
约束
- 所有输入值均为整数。
- 1 \le N \le 10^6
- 1 \le Q \le 3 \times 10^5
- 所有查询都满足以下约束:
- 1 \le p \le N
- 1 \le x \le 10^6
- 1 \le k \le 10^9
输入
输入由标准输入按以下格式给出:
N Q
\rm{Query}_1
\rm{Query}_2
\vdots
\rm{Query}_Q
在这里, \rm{Query}_i 代表 i第一个查询。
类型 1 查询按以下格式给出:
1 p x
类型 2 查询按以下格式给出:
2 p
类型 3 查询按以下格式给出:
3 k
输出
对于每种类型 2 查询,在一行上输出答案。
示例输入 1
5 5 2 3 1 2 1000000 3 4 2 2 2 3
示例输出 1
3 1 1000000
该输入包含 5 查询。
- 最初, A=(1,2,3,4,5).
- 的 1st 查询是类型 2:输出 A_3=3.
- 的 2第一个查询是类型 1:替换 A_2 与 1000000.
- 查询后, A=(1,1000000,3,4,5).
- 的 3rd 查询是类型 3: 重复操作“移动第一个元素 A 到最后” 4 次。
- 查询后, A=(5,1,1000000,3,4).
- 的 4第一个查询是类型 2:输出 A_2=1.
- 的 5第一个查询是类型 2:输出 A_3=1000000.
示例输入 2
1000000 2 1 1000000 999999 3 1000000000
示例输出 2
输出可能为空。