Uolevilla on ilmapalloja rivissä, ja häntä kiinnostaa tietyllä välillä olevien ilmapallojen korkeuksien summa. Pallojen lisäksi uolevi seuraa ilmavirtauksia, jotka ovat aina tietyllä korkeudella. Välillä tietyn välin ilmavirtaukset kaikki nousevat tai laskevat tietyn määrän. Jos ilmavirtaus nousee yli sen kohdalla olevan ilmapallon, ilmapallo myös nousee tälle korkeudelle.

Aluksi ilmapallot ja ilmavirtaukset ovat samoilla korkeuksilla.
Ilmavirtausten korkeudet voivat tulla negatiivisiksi.

Uolevi antaa sinulle kahdentyyppisiä kyselyitä:
1\ a\ b\ x: Välillä a \ldots b olevien ilmavirtausten korkeudet muuttuvat x:llä.
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. Ilmavirtaukset ovat aluksi samoissa kohdissa kuin ilmapallot.

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 2*10^{5}
• 1 \leq a \leq b \leq n
• 1 \leq y_{i} \leq 10^{6}
• -10^{6} \leq x \leq 10^{6}

Esimerkki

Syöte:

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

Tuloste:

10
8
23

Selitys:

Aluksi pallojen ja ilmavirtausten korkeudet ovat:

3 7 1 4 3
3 7 1 4 3

Ensimmäisen operaation jälkeen korkeudet ovat:

3 7 1 4 3
1 5 -1 2 3

Toisen operaation jälkeen korkeudet ovat:

3 7 2 5 6
1 5 2 5 6