Algorithms and Data Structures

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 (), representing the elements of the array. Each of the following 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: 0.3 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue