Задача 6C. Сумма ≡

Условие

Дан массив из N элементов, нужно научиться находить сумму чисел на отрезке.

Формат входного файла

Первая строка содержит два целых числа N и K — число чисел в массиве и количество запросов. (1 ≤ N ≤ 100 000), (0 ≤ K ≤ 100 000). Следующие K строк содержат запросы

• A i x — присвоить i-му элементу массива значение x (1 ≤ i ≤ n, 0 ≤ x ≤ 10⁹)
• Q l r — найти сумму чисел в массиве на позициях от l до r. (1 ≤ l ≤ r ≤ n)

Формат выходного файла

На каждый запрос вида Q l r нужно вывести единственное число — сумму на отрезке.

Ограничения

Примеры тестов

5 9
A 2 2
A 3 1
A 4 2
Q 1 1
Q 2 2
Q 3 3
Q 4 4
Q 5 5
Q 1 5

0
2
1
2
0
5