eolymp
bolt
Try our new interface for solving problems
Problems

Signs alternating

Signs alternating

Time limit 1 second
Memory limit 122 MiB

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]).

Input data

The first line contains positive integer n (1n10^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 (1m10^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 (1in, 1j10^4);

  • operation of the second type is given with three integers 1 l r (1lrn).

Output data

For each operation of the second type print in a separate line the corresponding alternating sum.

Examples

Input example #1
3
1 2 3
5
1 1 2
1 1 3
1 2 3
0 2 1
1 1 3
Output example #1
-1
2
-1
3