Мама подарила мальчику Диме машину времени. К сожалению, эта машина работает только со встроенным в нее массивом длины \textbf{n}. Она может привести массив к состоянию на любой момент времени. Массив в машине тоже не простой, а особенный. Дима может выбрать два числа --- \textbf{i} и \textbf{d} (\textbf{1} ≤ \textbf{i} ≤ \textbf{n}, \textbf{-1000} ≤ \textbf{d} ≤ \textbf{1000}), и к элементу массива с индексом \textbf{i} магически прибавится \textbf{d}. Дима играет со своим массивом, а мама время от времени задает ему вопросы --- какова сумма всех чисел в массиве с индексами от \textbf{f} до \textbf{t}? Дима легко справился с этими вопросами, сможете ли вы? \InputFile В первой строке находятся два целых числа \textbf{n} и \textbf{q} (\textbf{1} ≤ \textbf{n}, \textbf{q} ≤ \textbf{10^5}) --- количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано \textbf{n} чисел \textbf{a_1}, \textbf{a_2}, ..., \textbf{a_n} (\textbf{−1000} ≤ \textbf{a_i} ≤ \textbf{1000}) --- начальное состояние массива. В следующих \textbf{q} строках заданы операции и запросы. Первый символ в строке может быть \textbf{t}, \textbf{+} или \textbf{?}. Если строка начинается с \textbf{t}, то это описание операции с машиной времени. Тогда в строке содержится ещё одно число \textbf{i} (\textbf{1} ≤ \textbf{i}) --- номер операции или запроса, к состоянию перед выполнением которой возвращается массив. \textbf{i} всегда не более номера текущей операции. Если строка начинается с \textbf{+}, то это операция прибавления. Далее следуют \textbf{i} и \textbf{d}, ограничения на которые описаны в условии. Если строка начинается с \textbf{?}, то это запрос. Далее следуют числа \textbf{f} и \textbf{t} (\textbf{1} ≤ \textbf{f}, \textbf{t} ≤ \textbf{n}). \OutputFile Для каждого запроса выведите сумму чисел в массиве с индексами от \textbf{f} до \textbf{t}, по одному результату в строке.