Description

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

1. Global add (i.e., add to all numbers in the sequence).
2. Query the maximum subarray sum in an interval.

Input Format

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

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

Then follow $m$ lines, each describing one operation.

• $1\ x$ : Add $x$ to all numbers.
• $2\ l\ r$ : Query the maximum subarray sum in the interval $[l,r]$ (you may choose no elements; in this case the maximum subarray sum is $0$).

Output Format

For each query, output one number as the answer.

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

0
6
18
19

Hint

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

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

Translated by ChatGPT 5