Uolevilla on ilmapalloja rivissä, ja häntä kiinnostaa tietyllä välillä olevien ilmapallojen korkeuksien summa. Välillä kuitenkin ilmavirtaukset nostavat matalalla olevia palloja ylöspäin. Uolevi ei kuitenkaan ole säätieteilijä, joten hän ei osaa laskea näitä arvoja itse.

Uolevi antaa sinulle kahdentyyppisiä kyselyitä:
1\ a\ b\ x: kaikkien ilmapallojen, jotka ovat välillä a \ldots b ja joiden korkeus on alle x, korkeudeksi asetetaan x.
2\ a\ b: laske välillä a \ldots b olevien ilmapallojen korkeuksien summa.

Syöte

Ensimmäisellä rivillä on luvut n ja q, ilmapallojen määrä ja kyselyiden määrä
Toisella rivillä on n lukua y_{i}, ilmapallojen korkeudet aluksi
Tämän jälkeen seuraavalla q:lla rivillä on jokaisella yksi kysely.

Tuloste

Tulosta vastaus jokaiseen tyypin 2 kyselyyn.

Rajat

• 1\leq n, q \leq 10^{6}
• 1 \leq a \leq b \leq n
• 1 \leq y_{i}, x \leq 10^{9}

Esimerkki

Syöte:

5 5
5 3 7 1 2
2 1 5
1 2 4 5
2 1 3
1 3 5 4
2 2 5

Tuloste:

18
17
21

Selitys:
Aluksi korkeudet ovat:

5 3 7 1 2

Ensimmäisen operaation jälkeen korkeudet ovat:

5 5 7 5 2

Toisen operaation jälkeen korkeudet ovat:

5 5 7 5 4