Array Manipulation Operations

You are given an array of n integers and q operations. There are two types of operations:

• Type 1: 1 l r x – Increment each element in the subarray from index l to r (1-indexed) by x.
• Type 2: 2 l r – Query the maximum value in the subarray from index l to r (1-indexed).

After processing all q operations, output the results of each query (Type 2) in the order they appear. Note that if there is no query operation, nothing should be printed.

The operations are executed in sequence, meaning that changes made by increment operations affect subsequent queries.

Formally, if we let \( A = [a_1, a_2, \dots, a_n] \) be the initial array, then for an operation of Type 1, for every index \( i \) satisfying \( l \le i \le r \), update \( a_i \) as follows:

\[ a_i \leftarrow a_i + x \]

For an operation of Type 2, report:

\[ \max_{l \le i \le r} a_i \]

inputFormat

The first line contains two integers n and q (the size of the array and the number of operations). The second line contains n space-separated integers representing the array. Each of the next q lines represents an operation in one of the following forms:

• For an increment operation: 1 l r x • For a query operation: 2 l r

All indices are 1-indexed.

outputFormat

For every query operation (Type 2), print the maximum value in the specified subarray on a new line. If there are no query operations, output nothing.## sample

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

5
8