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

Входные данные

Первая строка входных данных содержит два целых числа N и K - число чисел в массиве и количество запросов. (1 ≤ N ≤ 106); (1 ≤ K ≤ 105). Следующие K строк содержат запросы:

1: A i x – присвоить i-му элементу массива значение x (1 ≤ i ≤ n; 0 ≤ x ≤ 109)

2: Q l r – найти сумму чисел в массиве на позициях от l до r. (1 ≤ l ≤ r ≤ n)

Изначально в массиве живут нули.

Выходные данные

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