Implement the data structure from n elements a1, a2, ..., an that supports the next operations:

• assign to element ai the value j;
• find the alternating sum of segment from l to r inclusively, it est (al - al+1 + al+2 - ... ar).

Input

The first line contains positive integer n (1 ≤ n ≤ 105) - the length of array. Second line contains initial values of array - nonnegative integers, not greater than 104.

Third line contains positive integer m (1 ≤ m ≤ 105) - 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 ≤ 104);
• operation of the second type is given with three integers 1 l r (1 ≤ l ≤ r ≤ n).

Output

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