Range Update and Maximum Query

You are given an array a of length n (1-indexed) and q queries. There are two types of queries:

• Type 1: 1 l r x — For all indices i with \( l \le i \le r \), add x to a[i]. That is, for every i in the range, update \( a[i] = a[i] + x \).
• Type 2: 2 l r — Output the maximum value in the subarray from index l to r, i.e., compute \( \max_{l \le i \le r} a[i] \).

You need to process all the queries sequentially and print the result of every query of type 2. The queries are processed on the fly so that updates affect subsequent queries.

inputFormat

The input is given via standard input (stdin) in the following format:

T
n1 q1
a[1] a[2] ... a[n1]
(query_1 for test case 1)
(query_2 for test case 1)
...
n2 q2
a[1] a[2] ... a[n2]
(query_1 for test case 2)
...

Here, T denotes the number of test cases. For each test case, the first line contains two integers n and q representing the size of the array and the number of queries, respectively. The next line contains n integers representing the array elements. This is followed by q lines each describing a query in one of the two forms described above.

outputFormat

For each query of type 2, output the result (i.e., the maximum value in the specified subarray) on a separate line to standard output (stdout).

## sample

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

4
5
4
-1
0
2

</p>