Range Maximum Query with Updates

You are given an array of n integers and m operations. Each operation is one of the following two types:

• Update Operation: 1 x v, which adds the integer v to the element at position x (the positions are 1-indexed).
• Query Operation: 2 l r, which asks for the maximum value in the subarray from index l to index r (inclusive).

The operations modify the array in real-time. Use a segment tree data structure to efficiently process the updates and answer the queries. In terms of complexity, if we denote the size of the array by \( n \) and the number of operations by \( m \), the goal is to support both operations in \( O(\log n) \) time on average.

Note: The update operation is cumulative, i.e. the given v is added to the current value at the index rather than replacing it.

inputFormat

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

 n m
 a1 a2 ... an
 op1
 op2
 ...
 opm

where:

• n is the number of elements in the array.
• m is the number of operations.
• The second line contains n space-separated integers representing the initial array.
• Each of the following m lines describes an operation in one of the formats 1 x v or 2 l r (all indices are 1-indexed).

outputFormat

For each query operation (2 l r), output one line containing the maximum value in the interval \([l, r]\). The answers should be printed in the order the queries appear.

## sample

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

3
12
12

</p>