题目描述

有一个长度为 $ 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] $ 的子集。

输出格式

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

样例

input

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

output

18
13

数据范围与提示

$ n \leq 100000, m \leq 100000 $