Ever since Mr. DeMello forced you to clean the campus, he has been feeling remorseful, so he only asks you to maintain his new array.

Initially, he has $N$ elements and will make $Q$ queries of $2$ types:

1 i j: Update the element at index $i$ to have a value of $j$.

2 L R: Output the sum of every second element starting at $L$ (and including $L$) between $[L,R]$.

Constraints

For all subtasks:

$1\le N,Q\le 1000000$

$1\le i\le N$

$-1000000000\le A_i,j\le 1000000000$

$1\le L\le R\le N$

Subtask 1 [20%]

$1\le N,Q\le 5000$

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line will contain $N$ and $Q$, the number of elements and queries.

The next line will contain $N$ space-separated integers, $A_i$, the elements of the array.

The next $Q$ lines will contain one of the queries listed above.

Note: Fast I/O might be required to fully solve this problem (e.g., BufferedReader for Java).

Output Specification

For every type $2$ query, output the sum as specified.

Sample Input

5 5
1 5 6 9 3
2 1 5
2 2 5
1 2 -4
2 1 5
2 2 5

Sample Output

10
14
10
5