Implement the data structure from n elements a[1]
, a[2]
, ..., a[n]
that supports the next operations:
assign to element a[i]
the value j;
find the alternating sum of segment from l to r inclusively, it est (a[l]
- a[l+1]
+ a[l+2]
- ... a[r]
).
The first line contains positive integer n (1 ≤ n ≤ 10^5
) - the length of array. Second line contains initial values of array - nonnegative integers, not greater than 10^4
.
Third line contains positive integer m (1 ≤ m ≤ 10^5
) - the number of operations. In the next m lines the operations are given:
operation of the first type is given with three integers 0 i j (1 ≤ i ≤ n, 1 ≤ j ≤ 10^4
);
operation of the second type is given with three integers 1 l r (1 ≤ l ≤ r ≤ n).
For each operation of the second type print in a separate line the corresponding alternating sum.