Ääriarvot

• Time limit: 1.00 s
• Memory limit: 128 MB

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