Діма та машина часу
Мама подарувала хлопчику Дімі машину часу. Нажаль, ця машина працює лише з вмонтованим у неї масивом довжины 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, по одному результату в рядку.