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