Діма та великий масив
Мама подарувала хлопчику Дімі масив довжиною n. Масив цей не простий, а особливий. Діма може вибрати два числа i та d (1 ≤ i ≤ n, -1000 ≤ d ≤ 1000), і до елементу з індексом i магічно додається d. Діма бавиться зі своїм масивом, а мама час від часу задає йому питання - яка сума усіх чисел у масиві з індексами від f до t? Проте мама дуже зайнята і не може задавати питання так часто, як звичайно - усього вона задала не більше 1000 запитань. Діма легко справився з цими запитаннями, а чи зможете Ви?
Вхідні дані
У першому рядку знаходиться два цілих числа n та q (1 ≤ n ≤ 10^6, 1 ≤ q ≤ 5 ·10^5) - кількість елементів у масиві і сумарна кількість операцій та запитів відповідно. У наступному рядку задано n чисел a[1], a[2], ..., a[n] (-1000 ≤ a[i] ≤ 1000) - початковий стан масиву. У наступних q рядках задані операції та запити. Перший символ у рядку може бути + або ?. Якщо рядок починається з +, то це операція додавання. Далі йдуть i та d, обмеження на які описано в умові. Якщо рядок починається з ?, то це запит. Далі йдуть числа f і t (1 ≤ f, t ≤ n).
Вихідні дані
Для кожного запиту виведіть суму чисел у масиві з індексами від f до t, по одному результату у рядку.