Description

Given an integer sequence $a$, support two operations:

• 1 l r x means adding $x$ to every number in the interval $[l,r]$.
• 2 l r means querying the maximum subarray sum of the interval $[l,r]$ (it may be empty).

Input Format

The first line contains two positive integers $n,q$, representing the length of the sequence and the number of operations. The next line contains $n$ integers, representing the initial sequence $a$. Then there are $q$ lines, each containing several integers, representing one operation.

Output Format

For each operation of type 2, output one line with one integer representing the answer.

5 5
-2 -3 -3 -3 -3
2 1 5
1 2 4 4
2 1 5
1 2 3 1
2 3 3

0
3
2

Hint

Constraints
For $20\%$ of the testdata, $1\le n,q \le 1000$. For $60\%$ of the testdata, $1\le n,q \le 10^5$. For $100\%$ of the testdata, $1\le n,q \le 4\times 10^5$, $|a_i| \le 10^9$, $1 \le x \le 10^6$.

Idea: nzhtl1477. Solution: EntropyIncreaser. Code: EntropyIncreaser. Data: NaCly_Fish.

Please pay attention to constant-factor optimization.

Translated by ChatGPT 5