Det er $n$ pakker, nummerert fra $1$ til $n$, som nettopp har ankommet et lager. De kom i rekkefølgen $a_1, \dots, a_n$, og vi ønsker å sortere dem slik at de er i rekkefølgen $1, 2, \dots, n$.

Sorteringsmaskinen på lageret jobber i faser. Hver fase tar imot en rad $a_1, \dots, a_n$ med pakker og går frem som følger: Først legges den første pakken $a_1$ i en ny rad. Deretter, for hver pakke $a_i$ for $i = 2, \dots, n$, hvis $a_i$ er større enn den siste pakken (lengst til høyre) i den nye raden, legger maskinen den på slutten av raden. Ellers legger den pakken først i raden.

Hvis den nye raden ikke er sortert, fungerer den som inndata til neste fase av sorteringsmaskinen.

Skriv et program som hjelper til med å teste om maskinen fungerer som tiltenkt ved å svare på spørringer på formen «hvilken pakke er på den $b$-te plassen etter $t$ faser».

Inndata

Den første linjen i inndataene inneholder to heltall $n$ og $q$ ($1 \le n, q \le 5 \cdot 10^5$), som angir henholdsvis antall pakker og antall spørringer.

Den andre linjen inneholder en sekvens av $n$ heltall $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$) som representerer den opprinnelige rekkefølgen på pakkene.

De neste $q$ linjene inneholder spørringer; den $i$-te linjen inneholder to heltall $t_i$ og $b_i$ ($0 \le t_i \le 10^9$, $1 \le b_i \le n$), som angir den $i$-te spørringen.

Utdata

Skriv ut nøyaktig $q$ linjer. Den $i$-te linjen skal inneholde svaret på den $i$-te spørringen.

Hvis maskinen utførte færre enn $t_i$ faser, skriv $-1$. Ellers, skriv hvilken pakke som er på posisjon $b_i$ fra venstre etter at $t_i$ faser er utført.

Eksempler

Inndata 1

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

Utdata 1

4
2
-1
5

Forklaring 1

Maskinen vil utføre tre faser:

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

Inndata 2

1 1
1
1 1

Utdata 2

-1