U125195 大战杀马特(smart)

社会你虎哥和杀马特团长作为东百忍术界最大的两股势力的头领，即将在沈阳大街展开决战。

社会你虎哥派出了他的得意弟子小亮打头阵。小亮有一些技能（比如后空翻、倒立等），每次他可以从中选出两个组成大招放出。 具体地说，小亮一共装备了 $n$ 个技能，第 $i$ 个技能有效果值 $a_i$ 。小亮每次可以选择两个数 $l,r (l\leq r)$ 并将这两个技能组成大招放出，产生的伤害值为 $a_l-a_r$ 。 虎哥在小亮作战时会根据场上形势下达 $m$ 个指令，已知指令有两种。一是加 buff，虎哥会给出三个数 $l,r,x$，并施加一个 buff 使得小亮的第 $l$ 个技能到第 $r$ 个技能效果值 $+x$。二是攻击，虎哥会给出三个数 $l,r,k$，让小亮在区间 $[l,r]$ 中选出技能打出 $k$ 个大招。为了出其不意，这 $k$ 个大招必须两两不相同（不同攻击操作使用的大招之间没有限制）。 两个大招相同的定义是对于他们所使用的技能对 $(a_{l_0},a_{r_0})$，$(a_{l_1},a_{r_1})$，$l_0=l_1$ 且 $r_0=r_1$。 作为杀马特军团派来的内鬼——刀哥，你希望对于虎哥的每一次攻击指令都能快速获知小亮最多能打出多少伤害，以提醒杀马特团长注意提防。

无

无

**样例解释1** 第一次攻击指令，小亮可以释放技能对为 $(a_4,a_4),(a_4,a_5),(a_4,a_6)$ 的三个大招，产生的伤害为 $(5-5)+(5-1)+(5-4)=5$ 第二次攻击指令，小亮可以释放技能对为 $(a_3,a_5),(a_4,a_5)$ 的两个大招，产生的伤害为 $(4-1)+(5-1)=7$ 第三次攻击指令，此时技能序列变为了 $[-1,-1,2,4,2,5]$，小亮可以释放技能对为 $(a_2,a_2),(a_3,a_3),(a_3,a_5),(a_4,a_4),(a_4,a_5)$ 的五个大招，产生的伤害为 $(-1-(-1))+(2-2)+(2-2)+(4-4)+(4-2)=2$ **数据范围** 对于测试点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$ 次互不完全相同的大招 伤害值可以是负数，你可以理解为大招过于拉跨以至于给对面进行了治疗