C - 可旋转数组

问题描述

有一个初始为A_i = i的长度为N的整数序列A。需要处理Q个以下类型的查询：

1. 类型1：将A_p修改为x
2. 类型2：输出A_p的值
3. 类型3：执行k次"将数组第一个元素移动到末尾"的操作

形式化地说，类型3操作就是将A替换为(A_2,A_3,...,A_N,A_1)共k次。

约束条件

所有输入值都是整数。

• 1 ≤ N ≤ 1e6
• 1 ≤ Q ≤ 3e5
• 对于所有查询：
  • 1 ≤ p ≤ N
  • 1 ≤ x ≤ 1e6
  • 1 ≤ k ≤ 1e9

输入格式

输入通过标准输入给出，格式如下：

N Q
Query1
Query2
...
QueryQ

其中Queryi表示第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

样例解释1

初始数组A=(1,2,3,4,5)

1. 第1个查询(类型2)：输出A_3=3
2. 第2个查询(类型1)：将A_2改为1000000 → A=(1,1000000,3,4,5)
3. 第3个查询(类型3)：执行4次旋转操作 → A=(5,1,1000000,3,4)
4. 第4个查询(类型2)：输出A_2=1
5. 第5个查询(类型2)：输出A_3=1000000

样例输入2

1000000 2
1 1000000 999999
3 1000000000

样例输出2

可能没输出