Circus Cage Operations

In a large circus, there are n cages arranged in a straight line and numbered from 1 to n. Each cage has a maximum capacity provided in an array max_animals where the i-th element represents the maximum number of animals that can be accommodated in cage i (i.e. \(max\_animals[i]\)).

The circus performs two types of operations:

• Add animals: Represented as 1 u v. Here, \(u\) (with \(1 \le u \le n\)) denotes the cage index, and \(v\) is the number of animals to be added. When adding animals, the total in the cage must not exceed its maximum capacity.
• Query animals: Represented as 2 l r. Here, \(l\) and \(r\) (with \(1 \le l \le r \le n\)) denote the range of cages. The operation should return the total number of animals among those cages from index \(l\) to \(r\) inclusive.

You are required to process a sequence of m operations and print the result for each query operation.

inputFormat

The first line contains two integers, n and m, where n is the number of cages and m is the number of operations.

The second line contains n space-separated integers representing the maximum capacity of each cage (max_animals).

The following m lines each describe an operation. An operation is given in one of the following two formats:

• 1 u v: Add v animals to the cage with index u (making sure the cage does not exceed its maximum capacity).
• 2 l r: Query and print the total number of animals in cages from index l to r (inclusive).

outputFormat

For each query operation (i.e. operations of the form 2 l r), print the result on a new line.

## sample

5 5
10 5 8 7 9
1 2 3
1 1 6
2 1 3
1 3 4
2 1 4

9
13

</p>