说明

时间限制：1 Sec 内存限制：256 MB 输入文件：query.in 输出文件：query.out

给定长度为 $N$ 的数列 $A = \{a_1,a_2,\dots,a_N\}$。

一共给出 $Q$ 次询问，请依次处理所有操作，仅有一种询问类型：

操作：$1$ $l$ $r$ $x$

输出区间 $[l,r]$ 内 $\max(a_i - x, 0)$ 的总和，即：$\sum_{i=l}^{r} \max(a_i - x, 0)$

输入格式

第一行两个整数 $N,Q$。

第二行 $N$ 个整数 $a_1,a_2,\dots,a_N$。

接下来 $Q$ 行，每行给出一条询问 $1$ $l$ $r$ $x$。

输出格式

对每一条询问，单独输出一行对应的求和结果。

样例

样例 1

5 4
13 3 3 133 1333
1 1 5 1
1 1 5 100
1 2 3 3
1 4 5 33

1480
1266
0
1400

样例说明：

数组：$[13,3,3,133,1333]$

1. $x=1$：$(13-1)+(3-1)+(3-1)+(133-1)+(1333-1) = 12+2+2+132+1332 = 1480$

2. $x=100$：$\max(13-100,0)+\max(3-100,0)+\max(3-100,0)+(133-100)+(1333-100)=0+0+0+33+1233=1266$

3. $x=3$：区间$[2,3]$ 值为 $3,3$，每项 $\max(3-3,0)=0$，总和 $0$

4. $x=33$：区间$[4,5]$，$(133-33)+(1333-33)=100+1300=1400$

数据范围

对于 50% 的数据，$N,Q,a_i,x \le 1000$。

对于 100% 的数据，$1 \le N,Q \le 10^5$，$1 \le a_i \le 10^9$，询问参数：$1 \le l \le r \le N$，$1 \le x \le 10^9$。