Chtholly has given you a sequence $a$ of length $n$, and there are $m$ operations:

1. Add $x$ to all numbers in the range $[l, r]$.
2. Query the maximum subarray sum in the range $[l, r]$. You may choose not to select any numbers (in which case the sum is $0$).

Input

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers representing the sequence $a$.

The following $m$ lines:

• 1 l r x: Add $x$ to all numbers in the range $[l, r]$.
• 2 l r: Query the maximum subarray sum in the range $[l, r]$.

Output

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

Examples

Input 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 1

0
3
2

Input 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 2

6
3
0

Subtasks

Idea: nzhtl1477, Solution: ccz181078, Code: nzhtl1477 & ccz181078 & mrsrz, Data: nzhtl1477 & mrsrz & w33z8kqrqk8zzzx33

$1 \le n, m \le 10^5$, $|a_i| \le 10^9$, $|x| \le 10^9$.

It is guaranteed that $|a_i| \le 2 \times 10^9$ at any time.

By nzhtl1477 & ccz181078