Professori Viherkasvin kukkapenkki on ollut monta viikkoa harvinaisten ahmattimatojen hyökkäyksen kohteena.

Madot hyökkäävät aina jonkin kukkapenkin välin kukkiin. Nimestään huolimatta ahmattimadot ovat oikeastaan aika nirsoja: Ne syövät itsensä aivan täyteen tai sitten eivät ollenkaan. Lisäksi ahmattimadot vihaavat erikokoisia ahmattimatoja, joten jokaiseen hyökkäykseen osallistuu aina vain yhdenkokoisia matoja. Yhdessä hyökkäyksessä on aina niin paljon matoja, että osa niistä jää aina nälkäisiksi.

Viherkasvi istuttaa myös välillä uusia kukkia kukkapenkkiin. Tällöin professori poistaa kaikki tietyn välin kukat ja korvaa ne uusilla kukilla.

Professori on kiinnostunut matojen hyökkäyksen vaikutuksesta, joten hän haluaa selvittää erilaisten välien kukkien pituuksien summia.

Viherkasvi haluaa siis tehdä seuraavia kyselyitä:
1\ a\ b\ x: vähennä kukkien a \ldots b pituudesta x niin kauan kunnes kukan pituus on pienempi kuin x
2\ a\ b\ x: Korvaa välin a \ldots b kukat uusilla kukilla, joiden pituus on aina x.
3\ a\ b: Laske välin a \ldots b kukkien pituuksien summa.

Syöte

Ensimmäisellä rivillä n ja q, missä n on kukkien määrä ja q on kyselyiden määrä.
Toisella rivillä on n lukua: kukkien pituudet aluksi.
Tämän jälkeen seuraavalla q rivillä on jokin kysely.

Tuloste

Tulosta vastaus jokaiseen tyypin 3 kyselyyn.

Rajat

• 1 \leq n, q \leq 10^{6}
• kukkien pituudet välillä [0, 10^{9}]

Esimerkki

Syöte:

10 10
384 887 778 916 794 336 387 493 650 422 
3 3 8
1 4 7 427
2 3 7 568
2 3 10 124
2 6 8 23
1 9 10 394
3 2 7
2 2 4 538
2 5 9 414
2 2 7 874

Tuloste:

3704
1305