题目描述

给你一个长度为 $N$ 的数列 $A$，初始时 $A_i=i$。

对 $A$ 执行以下操作共 $Q$ 个：

• 操作一：$A_p\leftarrow x$。
• 操作二：询问 $A_p$。
• 操作三：将 $A$ 循环左移 $k$ 个元素长度。
  • 形式化地，执行 $A\leftarrow (A_2,A_3,\cdots,A_N,A_1)$ 操作 $k$ 次。

输入格式

第一行两个整数 $N,Q(1\le N\le 10^6,1\le Q\le 3\times 10^5)$。 接下来 $Q$ 行，第一个数字表示操作类型。
对于操作一，接下来两个整数 $p,x$；
对于操作二，接下来一个整数 $p$；
对于操作三，接下来一个整数 $k$。
保证 $1\le p\le N,1\le x\le 10^6,1\le k\le 10^9$。

输出格式

对于每次操作二，输出一行一个整数表示回答。

输入输出样例 #1

输入 #1

5 5
2 3
1 2 1000000
3 4
2 2
2 3

输出 #1

3
1
1000000

输入输出样例 #2

输入 #2

1000000 2
1 1000000 999999
3 1000000000

输出 #2

说明/提示

样例 1 解释

有 $5$ 个询问。

• 初始时，$A=(1,2,3,4,5)$。
• 第一次操作，询问 $A_3=3$。
• 第二次操作，$A_2\leftarrow1000000$。$A=(1,1000000,3,4,5)$。
• 第三次操作，$A$ 循环左移 $4$ 个元素长度，$A=(5,1,1000000,3,4)$。
• 第四次操作：询问 $A_2=1$。
• 第五次操作：询问 $A_3=1000000$。

样例 2 解释

输出可能是空的。