Дима və massiv 1

Mama oğluna Dima uzunluğu $n$ olan bir massiv hədiyyə etdi. Bu massiv sadə deyil, xüsusi bir massivdir. Dima $i,j$ və $d(1\le i\le j\le n,-1000\le d\le 1000)$ üç ədəd seçə bilər və indeksləri $i$-dən $j$-yə qədər olan bütün elementlər sehrli şəkildə $d$-yə bərabər olur. Dima öz massiviylə oynayır və ana zaman-zaman ona sual verir — $f$-dən $t$-yə qədər indeksləri olan massivdəki bütün ədədlərin cəmi nədir? Dima bu suallarla asanlıqla başa çıxdı, bəs siz bacararsınızmı?

Giriş verilənləri

Birinci sətirdə iki tam ədəd $n$ və $q(1\le n\le 5\cdot 10^5,1\le q\le 10^5)$ — massivdəki elementlərin sayı və əməliyyatlar və sorğuların ümumi sayı. Növbəti sətirdə massivinin başlanğıc vəziyyəti olan $n$ ədəd $a_1,a_2,...,a_n(-1000\le a_i\le 1000)$ verilmişdir. Növbəti $q$ sətirdə əməliyyatlar və sorğular verilmişdir. Sətirin ilk simvolu $=$ və ya $?$ ola bilər. Əgər sətir $=$ ilə başlayırsa, bu, təyin etmə əməliyyatıdır. Sonra $i,j$ və $d$ gəlir, məhdudiyyətlər yuxarıda verilmişdir. Əgər sətir $?$ ilə başlayırsa, bu, sorğudur. Sonra $f$ və $t(1\le f,t\le n)$ ədədləri gəlir.

Çıxış verilənləri

Hər bir sorğu üçün $f$-dən $t$-yə qədər indeksləri olan massivdəki ədədlərin cəmini bir sətirdə çıxarın.

Nümunələr