Perform Array Queries

You are given an integer array (a_1, a_2, \dots, a_n) of length (n) and (q) queries. There are two types of queries:

1. Update Query (Type 1): Given four integers 1 k l r, add (k) to each element in the subarray from index (l) to (r) (inclusive). In other words, for every index (i) such that (l \le i \le r), perform:

[ a_i \leftarrow a_i + k ]

2. Maximum Query (Type 2): Given three integers 2 l r, output the maximum element in the subarray from index (l) to (r) (inclusive).

The queries are processed sequentially and the updates affect subsequent queries. Your task is to process the queries and for every Type 2 query, print the result on a new line.

inputFormat

The input is given on standard input in the following format:

• The first line contains two space-separated integers (n) and (q), denoting the size of the array and the number of queries, respectively.
• The second line contains (n) space-separated integers (a_1, a_2, \dots, a_n), representing the initial array.
• The next (q) lines each describe a query. A query is given in one of the following formats:
  • For a Type 1 query: 1 k l r where (k) is the value to add, and (l) and (r) denote the range (1-indexed) to update.
  • For a Type 2 query: 2 l r where (l) and (r) denote the range (1-indexed) in which to find the maximum.

outputFormat

For each Type 2 query, output the maximum element in the specified range on a new line. There is no output for Type 1 queries.## sample

8 5
4 2 7 1 3 5 8 6
1 3 2 4
2 1 4
2 5 7
1 -2 1 3
2 3 6

10
8
8