Mirko 厌倦了为不同的任务实现各种各样的数据结构。因此，他决定设计一种终极数据结构，使他能够操作自己最喜欢的数列。请帮助他！
Mirko 会给你他的初始数列，以及你需要执行的一系列操作。每个操作要么是查询信息，要么是修改现有数列。可用的操作类型如下表所示。
| 操作类型 | 描述 | 示例 |
|---|---|---|
1 A B X |
将第 $A$ 个到第 $B$ 个元素（包含端点）的值设为 $X$ | $(9, 8, 7, 6, 5, 4, 3, 2, 1)$ $\to \text{1 3 5 0} \to$ $(9, 8, 0, 0, 0, 4, 3, 2, 1)$ |
2 A B X |
将第 $A$ 个元素加上 $X$，第 $A+1$ 个元素加上 $2 \cdot X$，……，第 $B$ 个元素加上 $(B-A+1) \cdot X$ | $(9, 8, 7, 6, 5, 4, 3, 2, 1)$ $\to \text{2 3 5 2} \to$ $(9, 8, 9, 10, 11, 4, 3, 2, 1)$ |
3 C X |
在第 $C$ 个元素之前立即插入一个值为 $X$ 的新元素 | $(9, 8, 7, 6, 5, 4, 3, 2, 1)$ $\to \text{3 4 100} \to$ $(9, 8, 7, 100, 6, 5, 4, 3, 2, 1)$ |
4 A B |
计算第 $A$ 个到第 $B$ 个元素的所有元素之和 | $(2, 18, 7, 6, 1, 4, 7, 7, 2)$ $\to \text{4 6 7} \to$ 结果：$11$ |
输入格式
第一行包含两个整数 $N$ 和 $Q$（$1 \le N, Q \le 100\,000$），分别表示初始数列的长度和操作的数量。
第二行包含初始数列。数列由不超过 $100\,000$ 的非负整数组成，每个数之间用单个空格分隔。
接下来的 $Q$ 行包含上述格式的操作。在所有操作中，$1 \le X \le 100$，$1 \le A \le B \le \text{currentSequenceLength}$，且 $1 \le C \le \text{currentSequenceLength} + 1$。其中 $\text{currentSequenceLength}$ 表示执行该操作前数列的当前长度。
输出格式
对于每个类型为 4 的操作，输出一行，包含所求的和。
说明
注意：某些和可能会超出 32 位有符号整数的范围。
样例
输入样例 1
5 5 1 2 3 4 5 1 5 5 0 4 4 5 4 5 5 2 1 5 1 4 1 5
输出样例 1
4 0 25
输入样例 2
1 7 100 3 1 17 3 2 27 3 4 37 4 1 1 4 2 2 4 3 3 4 4 4
输出样例 2
17 27 100 37