T4 皮卡丘

题目信息

时间限制: 1s

空间限制: 256M

输入文件: pi.in

输出文件: pi.out

题目描述

小 D 的皮卡丘可以产生 $n$ 种不同的电压，第 $i$ 种电压值为 $a_i$。当皮卡丘需要释放电击技能时，需要选择两种电压 $l, r(l \leq r)$ 对应产生的电压值为 $a_l-a_r$。

小 D 对他的皮卡丘进行了 $m$ 次训练，训练有以下两种：

• 增幅训练，小 D 按照指标 $l, r, x$ 训练皮卡丘，使得皮卡丘能释放的第 $l$ 种电压到第 $r$ 种电压的电压值 $+=x$。
• 攻击训练，小 D 按照指标 $l, r, k$ 训练皮卡丘，皮卡丘在区间 $[l, r]$ 中选出电压值并打出 $k$ 次电击。为了提升训练效果，这 $k$ 次电击的组合方式必须两两不相同（不同攻击训练使用的电击技能之间没有限制）。两次电击的组合方式相同的定义是对于它们所使用的电压值对 $\left(a_{l_0}, a_{r_0}\right), \left(a_{l_1}, a_{r_1}\right)$ 有 $l_0=l_1$ 且 $r_0=r_1$。

小 D 想知道，在每次攻击训练时，皮卡丘最大能打出多少电击伤害？电击伤害定义为训练中所有电击技能电压值之和。

输入格式

第一行两个整数 $n, m$ 意义如题面所示。

接下来一行 $n$ 个整数，表示皮卡丘能释放的电压值。

接下来 $m$ 行每行表示一次训练：

• 增幅训练形如 $1\ l\ r\ x$
• 攻击训练形如 $2\ l\ r\ k$

输出格式

对于每次攻击训练，输出一行表示皮卡丘在这次训练中最高可以打出多少伤害。

样例

样例输入 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

样例输出 1

5
7
2

样例解释 1

第一次攻击训练，皮卡丘可以释放电击 $\left(a_4, a_4\right),\left(a_4, a_5\right),\left(a_4, a_6\right)$，产生的电击伤害为

第二次攻击训练，皮卡丘可以释放电击 $\left(a_3, a_5\right),\left(a_4, a_5\right)$，产生的电击伤害为

第三次攻击训练，此时电压序列变为了 $[-1,-1,2,4,2,5]$，皮卡丘可以释放电击 $\left(a_2, a_2\right),\left(a_3, a_3\right),\left(a_3, a_5\right),\left(a_4, a_4\right),\left(a_4, a_5\right)$，产生的电击伤害为

数据范围与提示

• 对于测试点 1-2，满足 $n, m \leq 100$
• 对于测试点 3-7，满足 $n, m \leq 1000, \sum k \leq 2000$
• 对于测试点 8-10，满足 $n, m \leq 1000$
• 对于测试点 11-13，满足 $k=1$
• 对于测试点 14-16，满足没有修改操作
• 对于测试点 17-20，没有特殊限制
• 对于所有的数据，$n, m \leq 10^5 ， 1 \leq l \leq r \leq n ， \Sigma k \leq 3 \times 10^5 ，-10^6 \leq a_i, x \leq 10^6$
• 保证每次攻击训练一定能打出 $k$ 次互不完全相同的电击
• 为了完成训练指标，皮卡丘有时不得不打出电压为负数的电击