Problem Description

Kadokawa has given you a sequence \(a\) of length \(n\) and there are \(m\) operations.

1. Add \(x\) to all numbers in the interval \([l, r]\).
2. Query the maximum subarray sum within the interval \([l, r]\), where not selecting any number is allowed.

Input Format

The first line contains two integers \(n\) and \(m\).

The second line contains \(n\) integers representing the sequence \(a\).

The next \(m\) lines:

• 1 l r x: Add \(x\) to all numbers in the interval \([l, r]\).
• 2 l r: Query the maximum subarray sum within the interval \([l, r]\).

Output Format

For each query, output a single integer representing the answer.

Sample Input and Output

Input Sample #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

Output Sample #1

0
3
2

Input Sample #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

Output Sample #2

6
3
0

Notes

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\).

Guaranteed that \(|a_i| \leq 2 \times 10^9\) at any time.

By nzhtl1477 & ccz181078

见题面 Input 部分

见题面 Output 部分