珂朵莉给了你一个长为 $n$ 的序列 $a$，有 $m$ 次操作。

1. 把区间 $[l,r]$ 内所有数都加上 $x$。
2. 查询区间 $[l,r]$ 内的最大子段和，可以不选数。

输入格式

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

第二行 $n$ 个整数表示序列 $a$。

后面 $m$ 行：

• 1 l r x：把区间 $[l,r]$ 内所有数加上 $x$。
• 2 l r：查询区间 $[l,r]$ 的最大子段和。

输出格式

对于每个询问，输出一个数表示答案。

样例数据

样例 1 输入

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

样例 1 输出

0
3
2

样例 2 输入

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

样例 2 输出

6
3
0

子任务

Idea：nzhtl1477，Solution：ccz181078，Code：nzhtl1477&ccz181078&mrsrz，Data：nzhtl1477&mrsrz&w33z8kqrqk8zzzx33

$1 \le n , m \le 10^5$，$| a_i | \leq 10^9$，$|x|\leq 10^9$。

保证任意时刻 $|a_i|\leq 2\times 10^9$。

By nzhtl1477 & ccz181078