Dimanın anası oğluna n uzunluqlu massiv hədiyyə etdi. Bu massiv heç də sadə deyil, o qeyri adidir. Dima massivdən iki ədəd seçə bilər : i və d (1 ≤ i ≤ n, -1000 ≤ d ≤ 1000) və bu halda i indeksli bütün elementlər möcüzəli şəkildə d-ə bərabər olacaq. Beləliklə, Dima öz massivi ilə oynayır, anası isə vaxtaşırı ona suallar verir : massivdə indeksi f-dən t-dək olan ədədlərin cəmi nəyə bərabərdir? Lakin, anası çox məşğul olduğundan həmişəki kimi tez-tez suallar verə bilmir. O, 1000-dən artıq sual verə bilmədi. Dima bu sualların öhdəsindən asanlıqla gəldi. Bəs siz bacararsız?

Giriş verilənləri

Birinci sətirdə n və q (1 ≤ n ≤ 106, 1 ≤ q ≤ 5 ·105) tam ədədləri verilmişdir ki, bunlar uyğun olaraq - massivdəki elementlərin sayını və əməliyyatlar ilə sorğularının sayının cəmini göstərir. Növbəti sətirdə, massivin başlanğıc şəkli olan a1, a2, ..., an (-1000 ≤ ai ≤ 1000) hədlərini göstərən n ədəd verilir. Növbəti q sətirdə əməliyyatlar və sorğular verilir. Sətrin birinci simvolu + və ya ? ola bilər. Əgər sətir + işarəsi ilə başlayırsa, bu əlavə etmə əməliyyatıdır. Sonra yuxarıda verilən məhdudiyyətlər daxilində i və d ədədləri gəlir. Əgər sətir ? işarəsi ilə başlayırsa, bu sorğudur. Ardınca f və t (1 ≤ f, t ≤ n) ədədləri gəlir.

Çıxış verilənləri

Hər bir sorğu üçün massivdə indeksi f-dən t-dək olan ədədlərin cəmi hər sətirdə bir nəticə olmaqla ekrana verin.