Description

As stated, given a sequence, you need to perform the following two operations:

• Add $x$ to a certain number.
• Find the sum of all numbers in a given interval.

Input Format

The first line contains two positive integers $n, m$, representing the number of elements in the sequence and the total number of operations.

The second line contains $n$ space-separated integers, where the $i$-th number is the initial value of the $i$-th element of the sequence.

Each of the next $m$ lines contains $3$ integers describing an operation, as follows:

• 1 x k Meaning: add $k$ to the $x$-th number.
• 2 x y Meaning: output the sum of all numbers in the interval $[x, y]$.

Output Format

Output several lines of integers, which are the results of all type 2 operations.

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

14
16

Hint

Constraints

For $30\%$ of the testdata, $1 \le n \le 8$, $1 \le m \le 10$. For $70\%$ of the testdata, $1 \le n, m \le 10^4$. For $100\%$ of the testdata, $1 \le n, m \le 5 \times 10^5$.

It is guaranteed that at any time, the sum of any subarray of $a$ (including subarrays of length $1$ and length $n$) lies in the range $[-2^{31}, 2^{31})$.

Sample explanation:

Therefore, the output is $14$ and $16$.

Translated by ChatGPT 5