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

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