Bob has a sequence of integers ~A~ of length ~N~, indexed from ~1~ to ~N~. Bob will perform ~Q~ operations on this array. Each operation is one of the following two types:

• 0 L R x: For all indices ~i~ such that ~L \le i \le R~, Bob updates ~a[i]~ as ~\max(a[i], x)~

• 1 L R: Bob wants to find the maximum subarray sum in the range ~[L..R]~. That is, you must find the maximum possible sum of a subarray ~A[i..j]~ where ~L \le i \le j \le R~. Additionally, Bob allows empty subarrays, and their sum is considered to be 0.

Input

The first line of input contains two integers ~N~ (~1 \leq N \leq 10^5~) and ~Q~ (~1 \le Q \le 2 \times 10^5~), the number of elements in the array and the number of operations.

The second line of input contains ~N~ integers ~A_1, A_2, \dots, A_N~, (~-10^9 \leq A_i \leq 10^9~), representing the original array.

Each of the following ~Q~ lines contains one operation in one of the two formats 0 L R x or 1 L R.

Output

For every 1 L R operation, output a single line containing the answer to the maximum subarray sum query.

Constraints

Subtask	Points	Additional constraints
~1~	~10~	~N, Q \le 200~
~2~	~10~	~N, Q \leq 2\,000~
~3~	~25~	~L == R~ for all type ~0~ operations.
~4~	~20~	~L=1~, ~R=N~ for all type ~1~ operations.
~5~	~35~	No additional constraints

Sample Input

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

Sample Output

6
7
10
11

Explanation for Sample

• For the ~1~st query, the largest subarray sum is ~6~.
• For the ~2~nd query, the array changes to ~[2, -4, 6, -4, 5]~ and the max subarray sum is ~7~.
• For the ~3~rd query, the array changes to ~[2, -4, 6, -1, 5]~ and the max subarray sum is ~10~.
• For the ~4~th query, the array changes to ~[2, -1, 6, -1, 5]~ and the max subarray sum is ~11~.