You are given an integer sequence $a_1, a_2, \dots, a_n$ of length $n$ (which may contain negative numbers). There are $q$ operations, each of which is one of the following:

• 0 l r x: For $i = l, l+1, \dots, r$, update $a_i$ to $\max(a_i, x)$.
• 1 l r: Find the maximum subarray sum in the range $[l, r]$. That is: $\max(0, \max_{l\le u\le v\le r} (\sum_{i=u}^v a_i))$.

Input

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

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

The next $q$ lines each contain an operation in the format 0 l r x or 1 l r.

Output

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

Examples

Input 1

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

Output 1

6
7
10
11

Note 1

• For the first query, the sequence is $2, -4, 6, -5, 5$, and the maximum subarray sum is $6$.
• For the second query, the sequence is $2, -4, 6, -4, 5$, and the maximum subarray sum is $6+(-4)+5=7$.
• For the third query, the sequence is $2, -4, 6, -1, 5$, and the maximum subarray sum is $6+(-1)+5=10$.
• For the fourth query, the sequence is $2, -1, 6, -1, 5$, and the maximum subarray sum is $2+(-1)+6+(-1)+5=11$.

Constraints

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

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