Реализуйте структуру данных из n элементов a1, a2, ..., an, поддерживающую следующие операции:

• присвоить элементу ai значение j;
• найти знакочередующуюся сумму на отрезке от l до r включительно, т.е. (al - al+1 + al+2 - ... ar).

Входные данные

В первой строке содержится натуральное число n (1 ≤ n ≤ 105) - длина массива. Во второй строке записаны начальные значения элементов - неотрицательные целые числа, не превосходящие 104.

В третьей строке находится натуральное число m (1 ≤ m ≤ 105) - количество операций. В последующих m строках записаны операции:

• операция первого типа задаётся тремя числами 0 i j (1 ≤ i ≤ n, 1 ≤ j ≤ 104);
• операция второго типа задаётся тремя числами 1 l r (1 ≤ l ≤ r ≤ n).

Выходные данные

Для каждой операции второго типа выведите в отдельной строке соответствующую знакочередующуюся сумму.