Range Addition and Maximum Subarray Sum Query

You are given a sequence a of length \(n\) and \(m\) operations. Initially, the sequence is provided. There are two types of operations:

1. Update: Add an integer \(x\) to each element in the interval \([l,r]\), i.e. for every index \(i\) with \(l \le i \le r\), perform \(a_i = a_i + x\).
2. Query: Compute the maximum subarray sum in the interval \([l,r]\). In this problem, you are allowed to choose an empty subarray which has a sum of \(0\). (That is, the answer of a query is \(\max(0, \text{maximum subarray sum in } [l,r])\)).

Input Format: The first line contains two integers \(n\) and \(m\). The second line contains \(n\) integers representing the initial sequence. Then \(m\) lines follow, each representing an operation. An update operation is represented as "1 l r x" and a query operation as "2 l r".

Output Format: For each query operation, output the maximum subarray sum in the specified interval on a new line.

Note: It is guaranteed that the answer is always non-negative because an empty subarray (with sum 0) is permitted.

inputFormat

The first line has two integers \(n\) and \(m\), denoting 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.

Then \(m\) lines follow. Each line is in one of the following two formats:

• 1 l r x: Add \(x\) to every element in the interval \([l, r]\).
• 2 l r: Query the maximum subarray sum in the interval \([l, r]\) (an empty subarray with sum 0 is allowed).

outputFormat

For each query operation, output a single line containing one integer: the maximum subarray sum in the given interval.

sample

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

4
6
2