Varastoon on juuri saapunut $n$ pakettia, jotka on numeroitu $1$:stä $n$:ään. Ne saapuivat järjestyksessä $a_1, \dots, a_n$, ja haluamme järjestää ne siten, että ne ovat järjestyksessä $1, 2, \dots, n$.

Varaston lajittelukone toimii vaiheittain. Jokainen vaihe ottaa vastaan rivin paketteja $a_1, \dots, a_n$ ja etenee seuraavasti: Ensin ensimmäinen paketti $a_1$ laitetaan uuteen riviin. Sitten jokaiselle paketille $a_i$, kun $i = 2, \dots, n$, jos $a_i$ on suurempi kuin uuden rivin viimeinen (oikeanpuoleisin) paketti, kone laittaa sen rivin loppuun. Muussa tapauksessa se laittaa sen rivin alkuun.

Jos uusi rivi ei ole järjestyksessä, se toimii syötteenä lajittelukoneen seuraavalle vaiheelle.

Kirjoita ohjelma, joka auttaa testaamaan, toimiiko kone tarkoitetulla tavalla, vastaamalla muotoa "mikä paketti on $b$:nnellä paikalla $t$ vaiheen jälkeen" oleviin kyselyihin.

Syöte

Syötteen ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $q$ ($1 \le n, q \le 5 \cdot 10^5$), jotka ilmaisevat pakettien lukumäärän ja kyselyjen lukumäärän.

Toinen rivi sisältää $n$ kokonaisluvun jonon $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$), joka kuvaa pakettien alkuperäistä järjestystä.

Seuraavat $q$ riviä sisältävät kyselyt; $i$:s rivi sisältää kaksi kokonaislukua $t_i$ ja $b_i$ ($0 \le t_i \le 10^9$, $1 \le b_i \le n$), jotka kuvaavat $i$:ttä kyselyä.

Tuloste

Tulosta täsmälleen $q$ riviä. $i$:nnen rivin tulee sisältää vastaus $i$:nteen kyselyyn.

Jos kone suoritti vähemmän kuin $t_i$ vaihetta, tulosta $-1$. Muussa tapauksessa tulosta, mikä paketti on sijainnissa $b_i$ vasemmalta lukien, kun $t_i$ vaihetta on suoritettu.

Esimerkit

Syöte 1

5 4
2 1 3 5 4
1 1
3 2
4 1
0 4

Tuloste 1

4
2
-1
5

Huomautus 1

Kone suorittaa kolme vaihetta:

$$2\ 1\ 3\ 5\ 4 \to 4\ 1\ 2\ 3\ 5 \to 3\ 2\ 1\ 4\ 5 \to 1\ 2\ 3\ 4\ 5$$

Syöte 2

1 1
1
1 1

Tuloste 2

-1