题目描述

这是一道模板题。

给定数列 $a_1, a_2, \dots, a_n$，你需要依次进行 $q$ 个操作，操作有两类：

1. 1 l r x：给定 $l, r, x$，对于所有 $i \in [l, r]$，将 $a_i$ 加上 $x$；
2. 2 l r：给定 $l, r$，求 $\sum_{i = l}^{r} a_i$ 的值。

输入格式

第一行包含 $2$ 个正整数 $n, q$，表示数列长度和询问个数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示初始数列。

接下来 $q$ 行，每行一个操作，格式为：

• 1 l r x
• 2 l r

输出格式

对于每个 2 l r 操作，输出一行一个整数，表示区间和。

样例

输入样例 1

5 10
2 6 6 1 1
2 1 4
1 2 5 10
2 1 3
2 2 3
1 2 2 8
1 2 3 7
1 4 4 10
2 1 2
1 4 5 6
2 3 4

输出样例 1

15
34
32
33
50

样例解释

初始数列：$[2, 6, 6, 1, 1]$

• 第一个操作 2 1 4：询问区间 $[1, 4]$ 的和 = $2 + 6 + 6 + 1 = 15$。
• 第二个操作 1 2 5 10：将 $[2, 5]$ 加 $10$，数列变为 $[2, 16, 16, 11, 11]$。
• 第三个操作 2 1 3：询问 $[1, 3]$ 的和 = $2 + 16 + 16 = 34$。
• 第四个操作 2 2 3：询问 $[2, 3]$ 的和 = $16 + 16 = 32$。
• 第五个操作 1 2 2 8：将第 $2$ 个元素加 $8$，数列变为 $[2, 24, 16, 11, 11]$。
• 第六个操作 1 2 3 7：将 $[2, 3]$ 加 $7$，数列变为 $[2, 31, 23, 11, 11]$。
• 第七个操作 1 4 4 10：将第 $4$ 个元素加 $10$，数列变为 $[2, 31, 23, 21, 11]$。
• 第八个操作 2 1 2：询问 $[1, 2]$ 的和 = $2 + 31 = 33$。
• 第九个操作 1 4 5 6：将 $[4, 5]$ 加 $6$，数列变为 $[2, 31, 23, 27, 17]$。
• 第十个操作 2 3 4：询问 $[3, 4]$ 的和 = $23 + 27 = 50$。

数据范围

• $1 \leq n, q \leq 10^6$
• $|a_i| \leq 10^6$
• $1 \leq l \leq r \leq n$
• $|x| \leq 10^6$

时间限制：5000 ms
内存限制：524288 KB

提示

请使用高效的算法实现，建议使用树状数组（Fenwick Tree）或线段树（Segment Tree）的懒标记（Lazy Propagation）版本，以支持区间修改和区间查询。

输入输出量较大，建议使用快速的输入输出方式（例如 scanf / printf 或关闭同步的 cin / cout）。