Range Update and Maximum Query

You are given an array of N integers and a sequence of Q queries. There are two types of queries:

• Type 1: 1 L R x — for all indices i with L ≤ i ≤ R (1-indexed), add the integer x to arr[i].
• Type 2: 2 L R — output the maximum value in the subarray from index L to R (inclusive), after applying all updates so far.

Note that 1-indexing is used for positions in the array.

Implementation Detail: To solve this problem, you may use a difference array (also known as a prefix difference technique). For an update query, if you let \(diff[i]\) be a difference array such that the final value at index \(i\) becomes \(arr[i] + \sum_{j=0}^{i}diff[j]\), then an update of adding \(x\) to indices from \(L\) to \(R\) can be done by:

\[ diff[L-1] += x, \quad \text{and if } R < N \text{ then } diff[R] -= x. \]

For a maximum query, compute the prefix sum over the entire array to obtain the current value of each element, and then find the maximum within the query bounds.

inputFormat

The first line contains two space-separated integers N and Q, representing the number of elements in the array and the number of queries respectively.

The second line contains N space-separated integers, representing the initial array.

Each of the following Q lines represents a query in one of the two formats:

• 1 L R x for a range update query; or
• 2 L R for a range maximum query.

outputFormat

For each query of type 2, output a single line containing the maximum value within the specified subarray after processing all updates.

## sample

5 4
1 3 5 7 9
2 1 3
1 2 4 2
2 2 5
2 1 5

5
9
9

</p>