Дима и машина времени
Мама подарила мальчику Диме машину времени. К сожалению, эта машина работает только со встроенным в нее массивом длины n. Она может привести массив к состоянию на любой момент времени. Массив в машине тоже не простой, а особенный. Дима может выбрать три числа - i, j и d (1 ≤ i ≤ j ≤ n, -1000 ≤ d ≤ 1000), и ко всем элементам массива с индексами от i до j магически прибавится d. Дима играет со своим массивом, а мама время от времени задает ему вопросы - какова сумма всех чисел в массиве с индексами от f до t? Дима легко справился с этими вопросами, сможете ли вы?
Входные данные
В первой строке находятся два целых числа n и q (1 ≤ n, q ≤ 10^5) - количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано n чисел a[1], a[2], ..., a[n] (-1000 ≤ a[i] ≤ 1000) - начальное состояние массива. В следующих q строках заданы операции и запросы. Первый символ в строке может быть t, + или ?. Если строка начинается с t, то это описание операции с машиной времени. Тогда в строке содержится ещё одно число i (1 ≤ i) - номер операции или запроса, к состоянию перед выполнением которой возвращается массив. i всегда не более номера текущей операции. Если строка начинается с +, то это операция прибавления. Далее следуют i, j и d, ограничения на которые описаны в условии. Если строка начинается с ?, то это запрос. Далее следуют числа f и t (1 ≤ f, t ≤ n).
Выходные данные
Для каждого запроса выведите сумму чисел в массиве с индексами от f до t, по одному результату в строке.