AT_abc410_c [ABC410C] Rotatable Array

给你一个长度为 $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 解释** 有 $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 解释** 输出可能是空的。