CSES - Ilmapallot 2
  • Time limit: 3.00 s
  • Memory limit: 512 MB

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 x1\ a\ b\ x: Välillä aba \ldots b olevien ilmavirtausten korkeudet muuttuvat xx:llä.
2 a b2\ a\ b: laske välillä aba \ldots b olevien ilmapallojen korkeuksien summa.

Syöte

Ensimmäisellä rivillä on luvut nn ja qq, ilmapallojen määrä ja kyselyiden määrä
Toisella rivillä on nn lukua yiy_{i}, ilmapallojen korkeudet aluksi. Ilmavirtaukset ovat aluksi samoissa kohdissa kuin ilmapallot.

Tämän jälkeen seuraavalla qq:lla rivillä on jokaisella yksi kysely.

Tuloste

Tulosta vastaus jokaiseen tyypin 2 kyselyyn.

Rajat

  • 1n,q,21051 \leq n, q, \leq 2*10^{5}
  • 1abn1 \leq a \leq b \leq n
  • 1yi1061 \leq y_{i} \leq 10^{6}
  • 106x106-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