Maximum Subarray Sum with Range Update Operations

You are given an integer sequence (a_1, a_2, \dots, a_n) (which may contain negative numbers) and need to process (q) operations on it. Each operation is one of the following types:

• Operation of the form 0 l r x means that for every index \(i\) with \(l \le i \le r\), update \(a_i\) to \(\max(a_i, x)\).
• Operation of the form 1 l r asks you to compute the maximum subarray sum in the segment \([l, r]\). In other words, compute \[ \max\Bigl(0,\;\max_{l \le u \le v \le r}\Bigl(\sum_{i=u}^{v}a_i\Bigr)\Bigr)\,. \]

Note: The array indices are 1-indexed. You should output the result for each query operation.

inputFormat

The first line contains two integers (n) and (q) representing the number of elements in the array and the number of operations respectively. The second line contains (n) integers (a_1, a_2, \dots, a_n). The following (q) lines each describe an operation in one of the two following formats:

• 0 l r x: For each index \(i\) in the range \([l, r]\), update \(a_i\) to \(\max(a_i, x)\).
• 1 l r: Query for the maximum subarray sum in the subarray \(a_l, a_{l+1}, \dots, a_r\).

outputFormat

For each query operation (operations of type 1), output a single integer representing the maximum subarray sum in the specified range. If the maximum subarray sum is negative, output 0.

sample

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

4
15
5