Проста сума

Вхідні дані

Перший рядок вхідних даних містить два цілі числа $N$ і $K$ — кількість елементів у масиві та кількість запитів відповідно, $1 \leq N \leq 1 0^{6}$ 1 \leq N \leq 10^6, $1 \leq K \leq 1 0^{5}$ 1 \leq K \leq 10^5. Наступні $K$ рядків містять запити двох типів:

A $i$ $x$ — присвоїти $i$ -му елементу масиву значення $x$ , $1 \leq i \leq N$ 1 \leq i \leq N, $0 \leq x \leq 1 0^{9}$ 0 \leq x \leq 10^9.
Q $l$ $r$ — знайти суму чисел у масиві на позиціях від $l$ до $r$ , $1 \leq l \leq r \leq N$ 1 \leq l \leq r \leq N.

Спочатку всі елементи масиву дорівнюють нулю.

Вихідні дані

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

Приклади

Приклад 1

Loading