CSES - Summat
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Tien varrella on nn 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 nn ja qq: talojen määrä ja kyselyiden määrä. Talot on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n.

Seuraavalla rivillä on nn kokonaislukua t1,t2,,tnt_1,t_2,\ldots,t_n: kunkin talon asukkaiden määrä.

Sitten syötteessä on qq riviä, joista jokainen kuvaa yhden kyselyn. Jokainen rivi on yksi seuraavista:

  • ! kk xx: talon kk asukkaiden määräksi tulee xx
  • ? aa bb: laske asukkaiden yhteismäärä välin aba \ldots b taloissa

Tuloste

Ohjelmasi tulee tulostaa vastaus jokaiseen ?-kyselyyn.

Rajat

  • 1n,q1051 \le n, q \le 10^5
  • 1ti1091 \le t_i \le 10^9
  • 1kn1 \le k \le n
  • 1x1091 \le x \le 10^9
  • 1abn1 \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