Fenwick Tree 1

Problem Description

You are given $n$ numbers $a_1, a_2, a_3, \dots, a_n$.

Support $q$ operations:

1. 1 x d: set $a_x = d$.
2. 2 x: query $\sum_{i=1} ^x a_i$.

Input Format

The first line contains two integers $n, q$ ($1\leq n, q\leq 2 \times 10^5$).

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1\leq a_i\leq 10^9$).

The next $q$ lines each contain an operation of the form 1 x d or 2 x, with $1\leq x\leq n$ and $1\leq d\leq 10^9$ guaranteed.

Output Format

For each query, output one line containing the answer.

Sample Input

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

Sample Output

10
19
11