Мама подарувала хлопчику Дімі машину часу. Нажаль, ця машина працює лише з вмонтованим у неї масивом довжины \textbf{n}. Вона може відновити масив до стану на довільний момент часу. Масив у машині також не простий, а особливий. Діма може вибрати два числа --- \textbf{i} та \textbf{d} (\textbf{1} ≤ \textbf{i} ≤ \textbf{j} ≤ \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}, по одному результату в строке.