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

Вхідні дані

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

У третьому рядку знаходиться натуральне число $m$ ( $1 \leq m \leq 1 0^{5}$ 1 \leq m \leq 10^5) — кількість операцій. У наступних $m$ рядках записані операції:

операція першого типу задається трьома числами $0 i j$ ( $1 \leq i \leq n, 1 \leq j \leq 1 0^{4}$ 1 \leq i \leq n,\ 1 \leq j \leq 10^4);
операція другого типу задається трьома числами $1 l r$ ( $1 \leq l \leq r \leq n$ 1 \leq l \leq r \leq n).

Вихідні дані

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

Приклади

Приклад 1

Loading