Taco Query Operations

You are given an array of integers and required to perform a series of operations on it. There are two types of operations:

Type 1: Update query - For a given operation of the form 1 x l r, add an integer (x) to every element in the subarray from index (l) to (r) (inclusive). That is, for every index (i) where (l \le i \le r), update (a_i = a_i + x).

Type 2: Query operation - For a query of the form 2 l r, output the maximum value in the subarray (a_l, a_{l+1}, \ldots, a_r), i.e., output (\max(a_l, a_{l+1}, \ldots, a_r)).

Note that the array is 1-indexed in the input. Your task is to process all the queries in order and print the result for each type 2 query.

inputFormat

The first line contains two 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 next (q) lines describes a query. A query can be in one of the following forms:

• For an update operation: 1 x l r, meaning add (x) to every element from index (l) to (r) (inclusive).
• For a maximum query: 2 l r, meaning output the maximum value in the subarray from index (l) to (r> (inclusive).

outputFormat

For each query of type 2, print the maximum value in the specified subarray on a new line.## sample

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

6
5