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

Limits: 2 sec., 256 MiB

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

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

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

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

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

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

Input

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

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

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

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

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

Output

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

Constraints

\(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\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 4 1 0 3 3 7 2 4 1 2 3 2 4 7 1 2 3 1 1 6	8 5 10