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 elements and will make queries of types:
1 i j: Update the element at index to have a value of .
2 L R: Output the sum of every second element starting at (and including ) between .
For all subtasks:
Subtask 1 [20%]
Subtask 2 [80%]
No additional constraints.
The first line will contain and , the number of elements and queries.
The next line will contain space-separated integers, , the elements of the array.
The next 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 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