At the very end, Chtholly gives you a sequence of length $n$ and $m$ operations:

1. Global addition (add a value to all numbers in the sequence).
2. Query the maximum subarray sum in a range.

Input Format

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

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

The following $m$ lines each describe an operation:

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

Output Format

For each type 2 operation, output the result on a new line.

Constraints

$1 \leq n \leq 3 \times 10^5$, $1 \leq m \leq 6 \times 10^5$. The absolute value of the numbers in the sequence is $\leq 2 \times 10^9$. The absolute value of $x$ in operation 1 is $\leq 5 \times 10^7$.

Examples

Input 1

5 7
-10 -3 -2 -4 -5
2 2 4
1 5
2 2 4
1 3
2 1 5
1 2
2 3 5

Output 1

0
6
18
19

Note

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