题目描述

维护一个长度为 n 的整数序列并执行 m 次操作：1 l r add 将区间 [l,r] 内每个数加上 add；2 l r 查询区间和；3 l r 查询区间最大值。

输入格式

第一行输入 n、m，第二行输入 n 个整数。接下来 m 行按题目描述输入操作。满足 1 ≤ n,m ≤ 1000，1 ≤ l ≤ r ≤ n。

输出格式

每个类型 2 或类型 3 的操作输出一行查询结果。

输入样例 #1

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

输出样例 #1

6
3
9

输入样例 #2

5 5
25 28 1 4 7
1 3 3 4
2 4 5
3 5 5
1 1 3 7
2 2 2

输出样例 #2

11
7
35

输入样例 #3

5 5
1 4 7 10 13
1 1 1 1
2 2 3
3 3 5
1 4 5 4
2 5 5

输出样例 #3

11
13
17

数据范围

• 每组输入包含19 至 34 个数，共6 至 9 行。
• 输入整数的取值范围为 1 至 30。