Запити на проміжку значень

Обмеження: 2 сек., 256 МіБ

Зеник і Марічка розв’язують наступну задачу.

Задано масив із \(n\) цілих чисел \(a_i\).

Потрібно опрацювати \(q\) запитів наступних типів:

1. Знайти суму усіх елементів масиву, які не менші за \(l_j\) та не більші за \(r_j\).

2. Змінити значення елементу масиву \(a\) в позиції \(p_j\) на \(d_j\).

Ваше завдання — допомогти Зенику і Марічці опрацювати усі запити.

Вхідні дані

У першому рядку задано два цілі числа \(n\) та \(q\) — розмір масиву та кількість запитів відповідно.

У наступному рядку задано \(n\) цілих чисел \(a_i\) через пробіл — початкові значення елементів масиву. Елементи пронумеровані цілими числами від 1 до \(n\) включно.

У наступних \(q\) рядках задано запити, які описано вище, в тому порядку, в якому їх слід виконувати. Формат запитів наступний:

• 1 \(l_j\) \(r_j\) — запит першого типу на знаходження суми.

• 2 \(p_j\) \(d_j\) — запит другого типу на зміну значення елементу.

Вихідні дані

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

Обмеження

\(1 \le n, q \le 3 \cdot 10^5\).

\(1 \le p_j \le n\),

\(0 \le l_j \le r_j \le 10^6\),

\(0 \le a_i, d_j \le 10^6\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 4 1 0 3 3 7 2 4 1 2 3 2 4 7 1 2 3 1 1 6	8 5 10