Problem E
Hringvegurinn

Vegagerðin er að útfæra nýtt tölvukerfi til að halda utan um uppihalds- og viðgerðarkostnaði á vegum landsins. Fyrsta mál á dagskrá er að útfæra kerfið fyrir mikilvægasta veg landsins, hringveginn. Til að einfalda utanumhald er hringveginum fyrst skipt í $N$ jafn langa hluta og eru þeir númeraðir $1,2,\dots ,N$ þar sem $1$ er vegurinn sem liggur í vestur frá Akureyri og hlutarnir eru í vaxandi röð eftir því. Þá er hluti $N$ vegurinn austan við Akureyri. Kerfið þarf að styðja eftirfarandi aðgerðir. Hægt þarf að vera að skrá kostnað upp á $x$ fyrir hvern veghluta á einhverjum vegarkafla. Hægt þarf að vera að spyrja hver heildarkostnaður einhvers vegarkafla er hingað til. Loks þarf að vera hægt að breyta tölusetningu kerfisins svo hluti $1$ sé á nýjum stað. Vegarkafli merkir hér samfellt bil vegarhluta. Bilið $3,6$ eru hlutarnir $3,4,5,6$. Hins vegar ef við erum með $6$ hluta samtals er $5,2$ hlutarnir $5,6,1,2$. $3,3$ er bara hlutinn $3$. Eftir endurtölusetningu er áttun kerfisins áfram eins, þ.e. hlutarnir eru í vaxandi röð þegar ferðast er rangsælis. Snúningur um $1$ sæti þýðir þá að vegarhlutinn sem var númeraður $1$ er nú númeraður $N$ og vegarhlutinn sem var númeraður $2$ er nú númeraður $1$.

Inntak

Fyrsta línan inniheldur tvær heiltölur, fjölda vegarhluta $N$ og fjölda fyrirspurna $q$ ($1\le N\le {10}^6$, $1\le q\le {10}^4$). Næst fylgja $q$ línur, hver með einni fyrirspurn. Hver fyrirspurn er ein lína og byrjar á tölunni $1,2$ eða $3$. Ef talan er $1$ fylgir næst ein tala $t$ ($1\le t\le N$) sem merkir að hliðra eigi tölusetningunni um $t$ sæti rangsælis. Ef talan er $2$ fylgja næst þrjár heiltölur $l,r,x$ ($1\le l,r\le N$, $1\le x\le {10}^9$) sem merkir að uppfæra eigi heildarkostnað á vegarkaflanum frá $l$ til $r$ um $x$ á hvern hluta. Loks ef talan er $3$ fylgja tvær heiltölur $l,r$ ($1\le l,r\le N$) og á þá að prenta út heildarkostnað hingað til á vegarkaflanum frá $l$ til $r$.

Úttak

Skrifa á út eina línu fyrir hverja fyrirspurn sem byrjar á tölunni $3$ og samsvarandi úttaki er lýst að ofan.

Stigagjöf

Hópur	Stig	Takmarkanir
1	20	$1\le n\le 1000$
2	50	$l\le r$ í öllum vegarköflum og engar snúningsskipanir
3	30	Engar frekari takmarkanir

Sample Input 1	Sample Output 1
10 10 2 2 4 3 2 3 3 4 3 3 4 3 4 2 1 1 2 4 1 7 3 1 3 1 5 3 10 1 3 2 2	10 6 20 14 7