← 返回题目列表

AtCoder · abc410_c

F. 可旋转阵列

中文机器翻译题面 查看原题

分数: 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


输出可能为空。