Задача C. Сумма+присвоение на отрезке

Входной файл:sum.in   Ограничение времени:10 сек
Выходной файл:sum.out   Ограничение памяти:256 Мб

Условие

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

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

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

Изначально массив заполнен нулями.

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

На каждый запрос вида

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

Ограничения

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

Входной файл (sum.in) Выходной файл (sum.out)
1
5 9
A 2 3 2
A 3 5 1
A 4 5 2
Q 1 3
Q 2 2
Q 3 4
Q 4 5
Q 5 5
Q 1 5
3
2
3
4
2
7

0.115s 0.016s 13