时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给定一个长度为 \(n\) 的整数数组 \(a[1]、a[2]、…、a[n](-10^9 <= A[i] <= 10^9)\)，和 \(m\) 个操作：

　　操作1：1 \(i\ j\ d\) 把 \(a[i]..a[j]\) 的所有元素都值增加 \(d（-10^9 ≤ d ≤ 10^9）\);

　　操作2：2 \(i\ j\) 查询当前序列的连续子序列 \(a[i]..a[j]\) 中的最大值

【输入格式】

　　第一行包含两个整数 \(n\) 和 \(m\)，表示数组有 \(n\) 个元素，\(m\) 表示有 \(m\) 个查询操作；
　　接下来的一行包含 \(n\) 个整数，第 \(i\) 个整数表示 \(a[i]\)；
　　再接下来的 \(m\) 行，每行表示一个操作.

【输出格式】

　　按输入顺序输出操作2的结果。

【输入输出样例】

　Input

8 8
2 4 4 8 3 3 7 3
2 2 4
1 1 5 -1
2 2 4
2 3 7
1 3 8 2
1 2 6 -3 
2 3 7
2 3 6

　Output

8
7
7
9
6

【数据限制】

　　对于 \(100\%\) 的数据，\(1<n≤100,000，\)m≤180,000$。

【来源】

　　Mr.he