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