题目描述

小 D 的皮卡丘可以产生 $n$ 种电压，第 $i$ 种电压值为 $a_i$。皮卡丘释放一次电击时，选择两个下标 $i,j$，满足 $i\leq j$，产生的电击伤害为 $a_i-a_j$。

小 D 对皮卡丘进行了 $m$ 次训练，训练分为以下两种。

• 增幅训练：给定 $l,r,x$，将第 $l$ 种到第 $r$ 种电压值都增加 $x$。
• 攻击训练：给定 $l,r,k$，从满足 $l\leq i\leq j\leq r$ 的下标对 $(i,j)$ 中选择 $k$ 对，使产生的电击伤害总和最大。同一次攻击训练选择的下标对必须两两不同，不同攻击训练之间没有限制。

下标对是否相同只由两个下标决定。即使电压值相同，只要下标对不同，就属于不同的组合。允许 $i=j$，此时电击伤害为 $0$。为了完成规定的次数，有时必须选择伤害为负数的电击。

请输出每次攻击训练的最大总伤害。攻击训练不会改变电压值。

输入格式

从文件 pi.in 中读入数据。

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各电压的初始值。

接下来 $m$ 行，每行描述一次训练：

• 1 l r x 表示增幅训练。
• 2 l r k 表示攻击训练。

输出格式

输出到文件 pi.out 中。

对于每次攻击训练，输出一行一个整数，表示最大总伤害。

样例

样例1

6 5
1 1 4 5 1 4
2 4 6 3
2 1 6 2
1 1 4 -2
1 4 6 1
2 2 5 5

5
7
2

第一次攻击训练可以选择 $(4,4)$、$(4,5)$、$(4,6)$，总伤害为 $0+4+1=5$。

第二次可以选择 $(3,5)$、$(4,5)$，总伤害为 $3+4=7$。

最后一次攻击训练时，电压序列为 $[-1,-1,2,4,2,5]$。选择 $(2,2)$、$(3,3)$、$(3,5)$、$(4,4)$、$(4,5)$，总伤害为 $0+0+0+0+2=2$。

样例2

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

-4
0
0

第一次必须选择全部六个合法下标对，伤害分别为 $0,-1,-2,0,-1,0$，总和为 $-4$。

增幅训练后序列为 $[2,3,3]$，可以选择四个伤害为零的不同下标对 $(1,1)$、$(2,2)$、$(2,3)$、$(3,3)$，所以第二次攻击训练的答案为 $0$。

最后一次只有下标对 $(2,2)$ 可以选择，答案为 $0$。

样例 3

见选手目录下的 pi/pi3.in 与 pi/pi3.ans。

该组样例满足 $n,m\le1000$。

样例 4

见选手目录下的 pi/pi4.in 与 pi/pi4.ans。

该组样例满足特殊性质 A。

样例 5

见选手目录下的 pi/pi5.in 与 pi/pi5.ans。

该组样例满足特殊性质 B。

数据范围

对于所有数据，$1\leq n,m\leq 10^5$，$1\leq l\leq r\leq n$，初始电压及每次增幅满足 $-10^6\leq a_i,x\leq 10^6$。

所有攻击训练的 $k$ 之和不超过 $3\times10^5$。每次攻击训练满足 $1\leq k\leq (r-l+1)(r-l+2)/2$，保证能选出规定数量的不同下标对。训练后的电压值不受初始值范围限制。

测试点编号	特殊限制
$1\sim2$	$n,m\leq100$
$3\sim7$	$n,m\leq1000$，且所有攻击训练的 $k$ 之和不超过 $2000$
$8\sim10$	$n,m\leq1000$
$11\sim13$	特殊性质 A
$14\sim16$	特殊性质 B
$17\sim20$	无额外限制

特殊性质 A：每次攻击训练均满足 $k=1$。

特殊性质 B：没有增幅训练。

本题共有20个测试点，每个测试点5分，各点独立计分。