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 1\,000\,000~

~1 \le i \le N~

~-1\,000\,000\,000 \le A_i, j \le 1\,000\,000\,000~

~1 \le L \le R \le N~

Subtask 1 [20%]

~1 \le N, Q \le 5\,000~

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