CSES - Summat
  • Time limit: 1.00 s
  • Memory limit: 128 MB
Tien varrella on $n$ taloa. Tehtäväsi on pitää kirjaa talojen asukkaista ja toteuttaa kyselyt, joissa talon asukkaiden määrä muuttuu ja halutaan laskea asukkaiden yhteismäärä tietyn välin taloissa.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $q$: talojen määrä ja kyselyiden määrä. Talot on numeroitu kokonaisluvuin $1,2,\ldots,n$.

Seuraavalla rivillä on $n$ kokonaislukua $t_1,t_2,\ldots,t_n$: kunkin talon asukkaiden määrä.

Sitten syötteessä on $q$ riviä, joista jokainen kuvaa yhden kyselyn. Jokainen rivi on yksi seuraavista:
  • ! $k$ $x$: talon $k$ asukkaiden määräksi tulee $x$
  • ? $a$ $b$: laske asukkaiden yhteismäärä välin $a \ldots b$ taloissa
Tuloste

Ohjelmasi tulee tulostaa vastaus jokaiseen ?-kyselyyn.

Rajat
  • $1 \le n, q \le 10^5$
  • $1 \le t_i \le 10^9$
  • $1 \le k \le n$
  • $1 \le x \le 10^9$
  • $1 \le a \le b \le n$
Esimerkki

Syöte:
8 3
3 2 7 1 3 6 6 2
? 3 5
! 4 5
? 3 5


Tuloste:
11
15