eolymp
bolt
Try our new interface for solving problems
Problems

Dima and machine of time

Dima and machine of time

Time limit 2 seconds
Memory limit 256 MiB

Мама подарила мальчику Диме машину времени. К сожалению, эта машина работает только со встроенным в нее массивом длины n. Она может привести массив к состоянию на любой момент времени. Массив в машине тоже не простой, а особенный. Дима может выбрать два числа — i и d (1in, -1000d1000), и к элементу массива с индексом i магически прибавится d. Дима играет со своим массивом, а мама время от времени задает ему вопросы — какова сумма всех чисел в массиве с индексами от f до t? Дима легко справился с этими вопросами, сможете ли вы?

Input data

В первой строке находятся два целых числа n и q (1n, q10^5) — количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано n чисел a_1, a_2, ..., a_n (−1000a_i1000) — начальное состояние массива. В следующих q строках заданы операции и запросы. Первый символ в строке может быть t, + или ?. Если строка начинается с t, то это описание операции с машиной времени. Тогда в строке содержится ещё одно число i (1i) — номер операции или запроса, к состоянию перед выполнением которой возвращается массив. i всегда не более номера текущей операции. Если строка начинается с +, то это операция прибавления. Далее следуют i и d, ограничения на которые описаны в условии. Если строка начинается с ?, то это запрос. Далее следуют числа f и t (1f, tn).

Output data

Для каждого запроса выведите сумму чисел в массиве с индексами от f до t, по одному результату в строке.

Examples

Input example #1
3 5
1 2 3
? 1 3
+ 2 2
? 1 3
t 1
? 1 3
Output example #1
6
8
6
Author Egor Kulikov
Source Winter School Kharkov 2012