Dynamic Maximum Subarray Sum with Range Updates

You are given an integer sequence \(a\) of length \(n\). You need to support two types of operations:

• 1 l r x: Add the integer \(x\) to each element in the range \([l, r]\) (1-indexed).
• 2 l r: Query the maximum subarray sum in the interval \([l, r]\). Note that an empty subarray is allowed and its sum is \(0\).

Note: The maximum subarray sum of an interval is defined as \(\max(0, \max_{l \leq i \leq j \leq r} \sum_{k=i}^{j} a_k)\).

inputFormat

The first line contains two integers \(n\) and \(q\) denoting the size of the sequence and the number of operations, respectively.

The second line contains \(n\) integers denoting the initial elements of the sequence \(a\).

Each of the following \(q\) lines contains an operation in one of the following two formats:

• 1 l r x: Add \(x\) to each element in the range \([l, r]\).
• 2 l r: Output the maximum subarray sum in the interval \([l, r]\).

It is guaranteed that all indices are 1-indexed.

outputFormat

For each query of type 2, output a single line containing the maximum subarray sum of the specified interval.

sample

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

4
9
0
11