Дима и большой массив

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

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

В первой строке находятся два целых числа $n$ и $q(1\le n\le 10^6,1\le q\le 5\cdot 10^5)$ — количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано $n$ чисел $a_1,a_2,...,a_n(-1000\le a_i\le 1000)$ — начальное состояние массива. В следующих $q$ строках заданы операции и запросы. Первый символ в строке может быть '$+$' или '$?$'. Если строка начинается с '$+$', то это операция прибавления. Далее следуют $i$ и $d$, ограничения на которые описаны в условии. Если строка начинается с '$?$', то это запрос. Далее следуют числа **f** и $t(1\le f,t\le n)$.

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

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

Примеры