P5693 The Sixth Block Decomposition of EI

He said he solved the classic square-root complexity problem, but he withdrew it because he was afraid of causing a sensation .jpg. However, [EntropyIncreaser](https://www.luogu.com.cn/user/21423) did obtain a better solution for this problem.

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

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.

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

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