Description

Chtholly gives you a sequence $a$ of length $n$, and there are $m$ operations.

1. Add $x$ to all numbers in the interval $[l, r]$.
2. Query the maximum subarray sum in the interval $[l, r]$, where choosing no elements is allowed.

Input Format

The first line contains two integers $n, 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 interval $[l, r]$.
• 2 l r: query the maximum subarray sum in the interval $[l, r]$, with the empty subarray allowed.

Output Format

For each query, output one number 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

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

6
3
0

Hint

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

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

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

By nzhtl1477 & ccz181078.

Translated by ChatGPT 5