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