Description

There is an integer sequence $a_1,a_2,\cdots,a_n$ of length $n$ (it may contain negative numbers). Now perform $q$ operations on it. Each operation is one of the following:

• 0 l r x means for $[l,r]$, assign $a_i$ to $\max(a_i,x)$;
• 1 l r asks for the maximum subarray sum in the interval $[l,r]$, i.e. $\max(0, \max_{l\le u\le v\le r} (\sum_{i=u}^v a_i))$.

Input Format

The first line contains two positive integers $n,q$, representing the sequence length and the number of operations.

The second line contains $n$ positive integers $a_1,a_2,\cdots,a_n$, representing the initial sequence.

The next $q$ lines each are in the form 0 l r x or 1 l r, representing one operation.

Output Format

For each operation of the form 1 l r, output one integer per line, representing the answer.

5 7
2 -4 6 -5 5
1 1 5
0 1 5 -4
1 1 5
0 3 4 -1
1 1 5
0 1 3 -1
1 1 5

6
7
10
11

Hint

Sample Explanation

For sample $1$:

• At the 1st query, the sequence is $2,-4,6,-5,5$, and the maximum subarray sum is $6$.
• At the 2nd query, the sequence is $2,-4,6,-4,5$, and the maximum subarray sum is $7$.
• At the 3rd query, the sequence is $2,-4,6,-1,5$, and the maximum subarray sum is $10$.
• At the 4th query, the sequence is $2,-1,6,-1,5$, and the maximum subarray sum is $11$.

Constraints

For all testdata, $1\le n\le 10^5$, $1\le q\le 2\times 10^5$, $|a_i|, |x|\le 10^9$.

• For $10\%$ of the testdata, $n,q \le 200$.
• For another $10\%$ of the testdata, $n,q \le 2000$.
• For another $25\%$ of the testdata, each operation $0$ satisfies $l=r$ (i.e. only point updates).
• For another $20\%$ of the testdata, each operation $1$ satisfies $l=1,r=n$ (i.e. only global queries).
• For the remaining $35\%$ of the testdata, there are no special constraints.

There are 3 hack testdata points from the problem setter.

Translated by ChatGPT 5