Uolevi tekee usein hintavertailun tietyissä kotikatunsa kaupoissa. Uolevin ostoskorissa on vain yksi tuote: 1,5 litran pullo kolajuomaa. Uolevia kiinnostaa tietää, mikä on halvin hinta pullolle ja monessako kaupassa tämä hinta on voimassa.

Voisitko auttaa Uolevia tekemään hintavertailuja?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: kauppojen määrä. Kaupat on numeroitu kokonaisluvuin $1,2,\ldots,n$.

Seuraavalla rivillä on $n$ kokonaislukua $p_1,p_2,\ldots,p_n$: pullon hinta kussakin kaupassa aluksi.

Sitten syötteessä on kokonaisluku $q$: tapahtumien määrä.

Lopuksi syötteessä on $q$ riviä, joista jokainen kuvaa yhden tapahtuman. Jokaisella rivillä on ensin kokonaisluku $t$. Jos $t=1$, rivillä on vielä kokonaisluvut $k$ ja $x$. Tämä tarkoittaa, että pullon hinta kaupassa $k$ on tästä lähtien $x$. Jos $t=2$, rivillä on vielä kokonaisluvut $a$ ja $b$. Tällöin Uolevi tekee hintavertailun kaupoissa välillä $a \ldots b$.

Tuloste

Ohjelmasi tulee tulostaa jokaisen hintavertailun tulos omalle rivilleen. Ensimmäinen luku on halvin hinta, toinen on kauppojen määrä.

Rajat

• $1 \leq n \leq 10^5$
• $1 \leq q \leq 10^5$
• $1 \leq p_k \leq 10^9$
• $1 \leq t \leq 2$
• $1 \leq k \leq n$
• $1 \leq x \leq 10^9$
• $1 \leq a \leq b \leq n$

Esimerkki

Syöte:

5
1 3 3 7 3
3
2 2 5
1 4 2
2 2 5

Tuloste:

3 3
2 1