Dima və zaman maşını
Mama oğluna, Dima'ya zaman maşını hədiyyə etdi. Təəssüf ki, bu maşın yalnız içində quraşdırılmış uzunluğu n olan bir massivlə işləyir. O, massivi istənilən zaman nöqtəsinə qaytara bilər. Maşındakı massiv də sadə deyil, xüsusi bir massivdir. Dima üç ədəd - i, j və d (1 ≤ i ≤ j ≤ n, -1000 ≤ d ≤ 1000) seçə bilər və massivdəki i-dən j-yə qədər olan bütün elementlərə sehrli şəkildə d əlavə edə bilər. Dima öz massivi ilə oynayır, anası isə zaman-zaman ondan soruşur - f-dən t-yə qədər olan indekslərdəki bütün ədədlərin cəmi nədir? Dima bu suallarla asanlıqla başa çıxır, bəs siz bacararsınız?
Giriş məlumatları
Birinci sətirdə iki tam ədəd n və q (1 ≤ n, q ≤ 10^5) - massivdəki elementlərin sayı və əməliyyatlar və sorğuların ümumi sayı verilir. Növbəti sətirdə n ədəd a[1], a[2], ..., a[n] (-1000 ≤ a[i] ≤ 1000) - massivın başlanğıc vəziyyəti verilir. Növbəti q sətirdə əməliyyatlar və sorğular verilir. Sətirin ilk simvolu t, + və ya ? ola bilər. Əgər sətir t ilə başlayırsa, bu zaman maşını ilə əməliyyat təsviridir. Onda sətirdə daha bir ədəd i (1 ≤ i) var - massiv əməliyyat və ya sorğunun icrasından əvvəlki vəziyyətinə qaytarılır. i həmişə cari əməliyyat nömrəsindən çox deyil. Əgər sətir + ilə başlayırsa, bu əlavə əməliyyatıdır. Sonra i, j və d gəlir, bunların məhdudiyyətləri şərtdə təsvir edilmişdir. Əgər sətir ? ilə başlayırsa, bu sorğudur. Sonra f və t ədədləri gəlir (1 ≤ f, t ≤ n).
Çıxış məlumatları
Hər bir sorğu üçün f-dən t-yə qədər olan indekslərdəki ədədlərin cəmini bir sətirdə çıxarın.