Tien varrella on n taloa. Tehtäväsi on pitää kirjaa talojen asukkaista ja toteuttaa kyselyt, joissa talon asukkaiden määrä muuttuu ja halutaan selvittää tietyn välin pienin ja suurin asukkaiden määrä.

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: etsi pienin ja suurin asukkaiden määrä välin a \ldots b talossa

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:

1 7
3 7