B. Computer

所有的隧道终于被挖通，八万和其他参与救援的人员惊喜的发现塌方的隧道中间有一截车厢上有为数不少的幸存者。

当然，与之相对应的，他们也发现了无数遇难者，有些遇难者在塌方的时候就已死去，但有些...是因为不及时的救援而在漫长的等待中死去...甚至是八万挖通那条隧道前不久!

正如鲁迅在目睹 I 国留学生的种种行径后弃医从文那样，一位死者(是的，显然他受到了更大的冲击)决定转而学习计算机。

他在查阅了大量资料后发现，破坏显示屏后计算机仍然可以工作，这显然和他原来的想法严重不符。

于是，他设计了一款神奇的软件，运行这款软件的计算机会在显示屏被破坏后停止工作。完成整个软件的编写后，他决定对这个功能进行测试：

首先，他准备了在一条线上的编号从 $1$ 到 $n$ 的 $n$ 个位置，每个位置上叠着 $a_i$ 台大小相同的计算机显示屏。然后，他会进行 $m$ 次操作，每个操作为下述 $2$ 种之一：

• 0 x y t: 对于所有编号在 $[x,\ y]$ 范围内的位置，他会把枪架在 $t\times$单个显示屏高度 的地方扫射，显然，所有叠着超过 $t$ 个显示屏的位置都只会剩下下方的 $t$ 个显示屏所连接的计算机仍在工作(破坏一个显示屏后叠在这个显示屏上面的显示屏就会掉到这个显示屏原有的位置进而同样被扫射破坏)。
• 1 x y：数出所有编号在 $[x,\ y]$ 范围内的显示屏所连接的计算机一共还有几台仍在工作，并记录。

他获得了一些实验结果，但初学编程的他不知道是否正确，所以请你来写个程序来获得正确结果以便和他得到的实验结果相比较。

本题有多组测试数据，文件第一行为测试数据组数 $T(1\leq T\leq 10)$。

对于每一组测试数据，第一行为两个整数 $n,\ m(1\leq n,\ m\leq 8\times 10^4)$，含义如上所述。

第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

接下来有 $m$ 行，表示将要进行的操作，格式如上所述，输入保证合法。

输入由非负整数、空格、回车组成，每个非负整数均小于 $2^{31}$。

对于每一个 1 类操作，输出一行一个整数，表示在对应范围内的显示屏所连接的计算机一共还有几台仍在工作。

样例输入

1
5 3
1 2 3 4 5
1 1 5
0 3 5 3
1 1 5

样例输出

15
12