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]~.
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.
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).
For every type ~2~ query, output the sum as specified.
5 5 1 5 6 9 3 2 1 5 2 2 5 1 2 -4 2 1 5 2 2 5
10 14 10 5