期末周来临，正值各个课程大作业的危急存亡之秋，蒜斜的电脑坏了：因为一些未知原因，蒜斜存放在内存里的数据经常会损坏，变成随机的乱码。

大作业的 deadline 即将要到了，已经没有时间留给蒜斜去维修、更换电脑了。不过幸运的是，蒜斜电脑的硬盘还是正常的：所有硬盘上的读写操作都是可靠的。

你可以帮蒜斜编写一个能在这台坏掉的电脑上正确运行的高效程序吗？

B++

在本题中，你需要使用一个特殊的语言 B++ 来编写程序。

指令集

一个 B++ 程序由若干条指令组成。令 $N$ 为程序中指令的数量，$c_0, \dots, c_{N-1}$ 依次表示程序中包含的指令。在一般情况下，B++ 程序会从 $c_0$ 开始，按照编号递增的顺序依次运行。

B++ 包含了如下六种指令：

1. Goto v1 v2：读取数据 v1 和 v2 的值，假设分别为 $x,y$。如果 $x \neq 0$，那么程序会跳转到指令 $c_{y}$（即下一条执行的指令会变为 $c_y$）。
2. Move v1 v2：读取数据 v1 的值，并将这个值写入到数据 v2。
3. Calc op v1 v2 v3：读取数据 v1 和 v2 的值 $x$ 和 $y$，并将 $x$ op $y$ 的结果写入到数据 v3。在这条指令中，op 有如下几种选择：
   1. 算数运算符 +, -, *, /, %。这些运算的结果与 c++ 中对应的 32 位整数运算完全一致（包括结果溢出的情况）。
   2. 逻辑运算符 ==, !=, <, <=。这些运算的结果与 c++ 中对应的逻辑运算类似：如果 c++ 中结果为真，那么在 B++ 中结果为 $1$，否则为 $0$。
4. Read v：从标准输入中读取一个整数并写入到数据 v。
5. Write v：读取数据 v 的值并输出到标准输出中。
6. Exit：程序运行会立即终止。

一个 B++ 程序只有在运行 Exit 指令后才会正常终止。

数据模型

B++ 程序在运行的过程中，可以读写两片存储空间 $A$ 和 $B$：它们分别对应着蒜斜电脑的内存和硬盘。在本题中，$A$ 和 $B$ 均可被视为大小为 $10^5$ 的 32 位整数数组：它们合法的下标范围均为 $0$ 到 $99999$，且里面每一个元素的取值范围均为 $[-2^{31},2^{31})$。

在 B++ 中，数据的表示方式如下：

1. 任何 32 位的整数 $w$ 都代表了一个常量数据 w：(1) 读取这个数据的结果始终是整数 $w$；(2) 这个数据不能被写入。
2. r 是一个特殊的数据，它对应着蒜斜电脑上唯一的寄存器：r 可以被视为一个可以读写的全局变量。
3. 对于任意整数 $b \in [-10^5, 10^5]$ 和数据 v，A[b@v] 都是一个数据：对 A[b@v] 读写时，会先读取数据 v 的值 $x$，然后对应地读写 $A_{b+x}$。
4. 对于任意整数 $b \in [-10^5, 10^5]$ 和数据 v，B[b@v] 都是一个数据：对 B[b@v] 读写时，会先读取数据 v 的值 $x$，然后对应地读写 $B_{b+x}$。

特别地，当 $b=0$ 时，A[b@v] 和 B[b@v] 可以分别被简写为 A[v] 和 B[v]。 为了改善代码可读性，B++ 规定数据的嵌套层数不能超过 $3$ 层。在这个规定下：

1. -114514, A[123], A[100@B[r]] 都是合法的数据。
2. A[2@B[A[4]]] 不是合法的数据，因为它嵌套了 $4$ 层。

令 $U$ 是一个定义在 $[-2^{31},2^{31})$ 中所有整数上的均匀分布，即这个范围内的所有整数出现的概率都是 $2^{-32}$。最开始，$A$ 和 $B$ 中的每个元素以及寄存器 r 都会被赋值为 $U$ 产生的一个随机整数。

就如题目最开始所说的那样，蒜斜电脑的内存坏了，因此数组 $A$ 中的元素会时不时地因为一些未知原因被赋值成随机数。具体来说，在执行完 B++ 的每一条指令之后，$A$ 中的每一个元素都有独立的 $0.01\%$ 的概率被赋值为 $U$ 产生的一个随机整数。

时间开销

B++ 程序主要的时间开销在于对数据的读写：执行指令的其他开销都可以被忽略不计。数据读写的开销计算方式如下：

1. 读取常量数据 w 的开销为 $0$。
2. 读写寄存器 r 的开销为 $0$。
3. 读写 A[b@v] 的开销都等于读取 v 的开销加 $1$。
4. 读写 B[b@v] 的开销都等于读取 v 的开销加 $100$，因为读写硬盘会比读写内存慢很多。

一条指令的开销等于它读写数据的开销总和。举例来说，Goto A[1] B[2] 的开销是 $101$，Calc + A[-2@A[3]] r B[A[1]] 的开销是 $103$，Exit 的开销是 $0$。

B++ 程序运行的总开销等于它执行的所有指令的开销之和。

运行错误

B++ 程序主要的运行错误可以分为如下几类：

1. 运算错误：在执行 Calc 指令时除以 $0$ 或者对 $0$ 取模。
2. 内存错误：写入了一个常量数据或者试图以小于 $0$ 或者大于等于 $10^5$ 的下标读写 $A$ 或 $B$。
3. 指令错误：尝试执行一条编号小于 $0$ 或者大于等于 $N$ 的指令。

解释器

为了方便大家本地调试 B++ 程序，本题的下发文件中包含一个解释器 interpreter.cpp。

使用指南

你可以使用指令 g++ interpreter.cpp -o interpreter -std=c++11 来编译下发的解释器。注意，在编译时，你需要把 testlib.h 和 interpreter.cpp 放在同一个文件夹下。

在编译结束后，你可以使用指令 ./interpreter inp code oup 来运行解释器，其中 inp, code, oup 分别代表输入文件、B++源码以及输出文件。

inp 第一行包含了一个整数 $n$，表示提供给 code 的输入整数数量。接着，第二行包含了 $n$ 个空格隔开的整数，按照顺序表示了 $n$ 个输入整数。

oup 第一行包含了一个整数 $m$，表示 code 预期的输出数量。接着，第二行包含了 $m$ 个空格隔开的整数，按照顺序表示了 $m$ 个输出整数。

code 第一行包含了一个整数 $N (1 \leq N \leq 10^5)$，表示 B++ 源码包含的指令数。接下来 $N$ 行按照顺序描述了指令 $c_0$ 至 $c_{N-1}$。

解释器会将给定的代码重复运行 $100$ 遍。如果给定的代码在其中任何一次运行的时候出现了运行错误，那么解释器会立即报错并退出。如果始终没有出现运行错误，那么解释器就会统计并输出这 $100$ 遍运行的结果。结果有三种可能性：

1. 结果正确 (AC)：代码在 $2 \times 10^5$ 条指令内正常结束了，且输出与 oup 中的输出完全相同。
2. 答案错误 (WA)：代码在 $2 \times 10^5$ 条指令内正常结束了，但是输出与 oup 中的输出不完全一致。
3. 运行超时 (TLE)：在执行了超过 $2 \times 10^5$ 条指令后，代码仍然没有正常结束。

解释器的输出格式为 AC: a/100, WA: b/100, TLE: c/100, Max Cost: d，其中 $a,b,c$ 分别表示 $100$ 次运行中结果正确、答案错误和运行超时的出现次数（保证 $a+b+c=100$），$d$ 表示所有结果正确的运行的最大开销。

只有当 $a = 100$ 且 $d \leq 3 \times 10^6$ 的时候，解释器才会认为 code 在 inp 上的运行是正确的。其余情况都会被视为运行错误。

例子1

这个例子中的所有内容均包含在下发文件中。这个例子的任务是编写一个 B++ 程序来计算两个输入整数的和：

1. 文件 inp1 为 2\n1 2（其中 \n 表示换行符），表示提供给 B++ 程序两个输入 $1$ 和 $2$。
2. 文件 oup1 为 1\n3，表示 B++ 程序的期望输出是一个整数 $3$。

下面描述了一个 B++ 程序 (对应文件 code1_1)：

5
Read B[0]
Read B[1]
Calc + B[0] B[1] B[0]
Write B[0]
Exit

因为读写硬盘（数组 $B$）总是可靠的，这个程序保证会输出正确的答案。它的运行开销为 $100+100+300+100 = 600$。下面是解释器给出的结果：

ok AC: 100/100, WA: 0/100, TLE: 0/100, Max Cost: 600

为了加快运行效率，我们可以把计算给转移到内存上（对应文件 code1_2）：

5
Read A[0]
Read A[1]
Calc + A[0] A[1] A[0]
Write A[0]
Exit

这个程序的运行开销减少到了 $1+1+3+1=6$，但是它有可能会输出一个错误答案：因为读写内存（数组 $A$） 是不可靠的。当运行 $c_0, c_1,c_2$ 后 $A_0$ 没有损坏且运行 $c_1$ 后 $A_1$ 没有损坏时，这个程序可以输出正确答案：这个概率为 $(1-0.01\%)^4 \approx 99.96\%$。

但是因为解释器只会将程序重复运行 $100$ 遍，所以在比较大的概率下，解释器仍然会认为这个程序是正确的。下面是解释器可能给出的一个结果：

ok AC: 100/100, WA: 0/100, TLE: 0/100, Max Cost: 6

例子2

这个例子中的所有内容均包含在下发文件中。这个例子的任务是编写一个 B++ 程序来计算 $n$ 个输入的和。

1. 文件 inp2 为 15\n14 1 2 3 4 5 6 7 8 9 10 11 12 13 14（其中 \n 表示换行符），表示 $n = 14$，且这些数分别为 $1$ 到 $14$。
2. 文件 oup2 为 1\n105，表示 B++ 程序的期望输出是一个整数 $105$。

下面描述了一个 B++ 程序 (对应文件 code2_1)：

8
Read A[0]
Move 0 A[1]
Read A[2]
Calc + A[1] A[2] A[1]
Calc - A[0] 1 A[0]
Goto A[0] 2
Write A[1]
Exit

这个程序将 $n$ 读入到 $A_0$ 中，并用 Goto 实现了一个简单的循环。然而，在运行这个程序的时候，解释器可能会报告如下错误：

FAIL Require too many inputs

这是因为在运行的过程中，循环变量 $A_0$ 可能会损坏：这时循环的次数以及读入的次数可能会超过 $n$。

为了避免这一点，我们可以把循环变量存储到寄存器里（对应文件 code2_2）：

8
Read r
Move 0 A[1]
Read A[2]
Calc + A[1] A[2] A[1]
Calc - r 1 r
Goto r 2
Write A[1]
Exit

这个 B++ 程序就不会出现运行错误了。但是因为 $A_1$ 和 $A_2$ 可能会损坏，所以该程序可能会输出错误的结果。下面是解释器给出的一个可能的结果：

wrong answer AC: 98/100, WA: 2/100, TLE: 0/100, Max Cost: 58

任务

你的任务是用 B++ 实现一个最基本的数据结构问题。

给定一个长度为 $n$ 的整数数列 $x_1, \dots, x_n$。你需要处理 $m$ 个操作。操作有两种：

1. 1 p w，表示给 $x_p$ 加上 $w$。
2. 2 l r，表示询问 $x$ 数组上区间 $[l,r]$ 的和。

写解释器已经是一个大工程了。因此，为了降低出题人的工作量，在给定 $n,m$ 的情况下，其余输入数据都是按照如下方式随机生成的：

1. $x_i$ 服从 $[0, 10^6]$ 中所有整数上的均匀分布。
2. 每一个操作的类型是从 $\{1,2\}$ 中等概率随机选取的。
3. 对于第一类操作，$p$ 服从 $[1,n]$ 中所有整数上的均匀分布，$w$ 服从 $[0, 10^6]$ 中所有整数上的均匀分布。
4. 对于第二类操作，$(l,r)$ 从所有合法区间（共 $n(n+1)/2$ 个）中等概率随机选取。

输入格式

注意，这儿给出的是 B++ 程序的输入格式。

输入的前两个整数 $n,m(n,m \geq 1)$，表示 $x$ 的长度以及操作个数。

接下来 $n$ 个整数 $x_i$，表示 $x$ 中元素的初始值。输入的余下部分依次表述了 $m$ 个操作。

输出格式

注意，这儿给出的是 B++ 程序的输出格式。

对于每一个第二类操作，输出一个整数表示答案。

样例输入

14
3 3 1 2 3 2 1 2 1 2 3 2 2 3

样例输出

2
3 8

限制与约定

重要的事情需要再说一遍。下面是本题中需要留意的参数：

1. 存储空间 $A$ 和 $B$ 的下标范围为 $[0, 10^5)$ 中的整数。读写一次 $A$ 中元素的开销是 $1$，读写一次 $B$ 中元素的开销是 $100$。
2. 在每一条指令执行结束后，$A$ 中的每一个元素都会有独立的 $0.01\%$ 的概率被赋值为 $[-2^{31}, 2^{31})$ 中的随机整数。
3. 提交程序至多包含 $10^5$ 条指令，这些指令的编号从 $0$ 开始。
4. 在测试时，对于每组测试数据，提交程序都会被独立地运行 $100$ 遍。一次运行被视为正确的当且仅当：
   1. 提交程序的输出正确。
   2. 执行的指令条数不超过 $2 \times 10^5$。
   3. 执行的所有指令的总开销不超过 $3\times{10^6}$。
5. 对于一组测试数据，提交程序被视为正确当且仅当 $100$ 次运行都是正确的。

在评测每一次提交的时候，评测器都会使用不同的随机种子。因此，同一个程序的多次提交对应结果可能会略有波动。在比赛中，只要有一次提交满足对应的要求即可获得对应的分数，但是请注意每支队伍在一道题上最多提交 $16$ 次。

Small Task: $n \leq 100, m \leq 700$。

Large Task: $n,m \leq 700$。

保证每一个部分包含的测试数据数量不超过 $25$ 组。

下载

下发文件下载