Yrityksessä on n työntekijää, joilla jokaisella on tietty palkka. Tehtäväsi on pitää kirjaa palkoista ja vastata kyselyihin niihin liittyen.

Syöte

Syötteen ensimmäisellä rivillä on kaksi lukua n ja q: työntekijöiden määrä ja kyselyiden määrä. Työntekijät on numeroitu kokonaisluvuin 1,2,\ldots,n.

Seuraavalla rivillä on n kokonaislukua p_1,p_2,\ldots,p_n: kunkin työntekijän palkka.

Sitten syötteessä on q riviä, joista jokainen kuvaa yhden kyselyn. Rivin muoto on jompikumpi seuraavista:

• ! k x: muuta työntekijän k palkaksi x
• ? a b: monenko työntekijän palkka on välillä a \ldots b?

Tuloste

Ohjelmasi tulee tulostaa vastaus jokaiseen ?-kyselyyn.

Rajat

• 1 \le n, q \le 10^5
• 1 \le p_i \le 10^9
• 1 \le k \le n
• 1 \le x \le 10^9
• 1 \le a \le b \le 10^9

Esimerkki

Syöte:

5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3

Tuloste:

3
2