Знакочергування

Реалізуйте структуру даних з n елементів a[1], a[2], ..., a[n], які підтримують наступні операції:

• присвоїти елементу a[i] значення j;

• знайти знакочерегуючу суму на відрізку від l до r включно, тобто (a[l] - a[l+1] + a[l+2] - ... a[r]).

Вхідні дані

У першому рядку міститься натуральне число n (1 ≤ n ≤ 10^5) - довжина масиву. У другому рядку записано початкові значення елементів - невід'ємні цілі числа, які не перевищують 10^4.

У третьому рядку знаходиться натуральне число m (1 ≤ m ≤ 10^5) - кількість операцій. У наступних m рядках записані операції:

• операція першого типу задається трьома числами 0 i j (1 ≤ i ≤ n, 1 ≤ j ≤ 10^4);

• операція другого типу задається трьома числами 1 l r (1 ≤ l ≤ r ≤ n).

Вихідні дані

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

Приклади