Реалізуйте структуру даних з 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).

Вихідні дані

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