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.