Alternating Sum
You are given an array of
n integers and q queries. There are two types of queries: update the array at a given index p, and calculate the alternating sum of a subarray [l; r].The alternating sum of a subarray
[l; r] is defined as the sum of elements at even indices minus the sum of elements at odd indices within the subarray. In other words, if the subarray [l; r] has elements [], then the alternating sum is given by For each query of type 2, you need to calculate and print the alternating sum of the given subarray
[l; r].Input
The first line contains two integers
n and q, representing the size of the array and the number of queries, respectively (1 ≤ n, q ≤ ).
The second line contains n space-separated integers q lines represents a query and consists of either 1 l r or 2 p x, where 1 denotes a query to calculate the alternating sum of the subarray [l; r], and 2 indicates an update query at index p with value x (1 ≤ p ≤ n, 1 ≤ x ≤ , 1 ≤ l ≤ r ≤ n).Output
For each query of type 2, print the calculated alternating sum in a separate line.
Examples
Input | Output |
8 3
1 2 3 4 5 6 7 8
1 2 6
2 4 9
1 1 8 | 4
-9 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB