B. 优化器

分块和可持久化机制在现代计算机系统中得到了广泛运用（即分页和写时复制）。

其中，分块使得对数据的大规模操作的任务量得以均摊，可持久化机制则大大优化了复制数组的时空效率。

目前小 X 接到了一个设计数据系统的任务，其任务可以抽象为:

起始给定一个全部为零的整数数组 ，长度为 ，现在需要支持四种操作：

（假设目前共有 个数组，起始 ；所有标号从 开始计数）

• ，表示将 的 号元素到 号元素全部赋值为 。
• ，表示将 的 号元素到 号元素全部增加上 。
• ，表示将一个 复制为一个新的数组，编号顺延（即设置为操作前的 值）。
• ，表示查询 的 号元素的值。

小 X 希望你结合分块和可持久化的思想，利用实际数据特征，高效解决这一问题。

第一行两个正整数 ，表示数组的长度和操作的个数。

接下来 行，每行表示一个操作。其中第一个字符串为操作名，其后按照操作规范以空格分隔给出操作的参数。

对于每个 QUERY 操作，输出一个整数，表示对应的答案。

样例输入

5 10
COPY 0
COPY 1
SET 1 0 2 4
SET 2 3 3 1
QUERY 0 1
QUERY 2 4
QUERY 2 3
QUERY 1 1
SET 2 0 4 0
QUERY 2 3

样例输出

0
0
1
4
0

对于全部数据，。

操作分布和局部性条件：

• 在对操作没有特殊限制的情况下，COPY 操作出现的概率为 ，QUERY 操作出现的概率为 。
• 块内（块大小为 ）区间操作出现的概率是长区间操作出现的概率的四倍，且所有块内的操作可以被分成不超过 次针对同一个块的连续操作。
• 在所有的区间操作中，约有 的概率，是对 号数组进行操作的。

子任务：本题共有 20 个测试点，从 1 开始编号。

对于 1 ~ 12 号测试点，。

对于 13 ~ 20 号测试点，。

对于 13、14 号测试点，没有 COPY 操作。

对于 13、15、16 号测试点，所有的 ADD 和 SET 操作中 。