题目描述

有一个长度为 $n$ 的序列，要求支持三种操作：

• 1 l r x 将 $[l, r]$ 中的数增加 $x$，保证 $x \leq 10000$；
• 2 l r x 用 $[l, l + x]$ 中的数对应替换 $[r, r + x]$ 中的数；
• 3 l r 求 $[l, r]$ 中所有数的和。

输入格式

第一行两个正整数 $n, m$ 表示序列长度和操作数。
第二行 $n$ 个正整数表示初始序列中的数，保证每个数 $\leq 10000$。
接下来 $m$ 行，每行三或四个整数，对应一个操作。
保证操作的区间合法且为 $[1, n]$ 的子集。

输出格式

对每个操作三，单独输出一行表示答案。

样例

4 4
1 2 3 4
1 2 3 4
3 1 4
2 1 3 1
3 2 4

18
13

数据范围与提示

$n \leq 100000, m \leq 100000$