Мінімум

Limits: 2 sec., 256 MiB

Дано масив цілих чисел $a$, який містить $n$ елементів. Потрібно написати програму, яка буде вміти опрацьовувати запити двох типів:

• знайти суму всіх елементів масиву на проміжку від елемента з номером $s$ і до елемента з номером $f$;

• замінити значення елементу масиву з номером $p$ на ціле число $v$.

Input

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

У другому рядку $n$ натуральних чисел — елементи масиву.

В наступних $q$ рядках містяться запити, по одному запиту в рядку. Запит «знайти суму» починається зі слова query, за яким слідують два натуральні числа $s$ і $f$. Запит «замінити елемент» починається зі слова change, за яким слідують натуральні числа $p$ і $v$.

Output

Для кожного запиту «знайти суму», потрібно вивести результат в окремому рядку.

Constraints

$1 \le n, q \le 111111$,

$1 \le a_i \le 10^3$,

$1 \le s \le f \le n$,

$1 \le p \le n$,

$1 \le v \le 10^3$.

Samples