Það eru $n$ bögglar, númeraðir frá $1$ til $n$, sem voru rétt í þessu að koma í vöruhús. Þeir komu í röðinni $a_1, \dots, a_n$, og við viljum raða þeim þannig að þeir séu í röðinni $1, 2, \dots, n$.

Flokkunarvélin í vöruhúsinu vinnur í lotum. Hver lota tekur við röð $a_1, \dots, a_n$ af bögglum og vinnur á eftirfarandi hátt: Fyrst er fyrsti böggullinn $a_1$ settur í nýja röð. Síðan, fyrir hvern böggul $a_i$ fyrir $i = 2, \dots, n$, ef $a_i$ er stærri en síðasti (lengst til hægri) böggullinn í nýju röðinni, setur vélin hann aftast í röðina. Annars setur hún hann fremst í röðina.

Ef nýja röðin er ekki röðuð, þá verður hún inntakið fyrir næstu lotu flokkunarvélarinnar.

Skrifaðu forrit sem hjálpar til við að prófa hvort vélin virki eins og til er ætlast með því að svara fyrirspurnum á forminu „hvaða böggull er í $b$-ta sæti eftir $t$ lotur“.

Inntak

Fyrsta lína inntaksins inniheldur tvær heiltölur $n$ og $q$ ($1 \le n, q \le 5 \cdot 10^5$), sem tákna fjölda böggla og fjölda fyrirspurna.

Önnur línan inniheldur runu af $n$ heiltölum $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$) sem táknar upphaflega röðun bögglanna.

Næstu $q$ línur innihalda fyrirspurnir; $i$-ta línan inniheldur tvær heiltölur $t_i$ og $b_i$ ($0 \le t_i \le 10^9$, $1 \le b_i \le n$), sem tákna $i$-tu fyrirspurnina.

Úttak

Skrifið út nákvæmlega $q$ línur. $i$-ta línan á að innihalda svarið við $i$-tu fyrirspurninni.

Ef vélin framkvæmdi færri en $t_i$ lotur, skrifið $-1$. Annars skal skrifa hvaða böggull er í sæti $b_i$ frá vinstri eftir að $t_i$ lotur hafa verið framkvæmdar.

Dæmi

Inntak 1

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

Úttak 1

4
2
-1
5

Athugasemd 1

Vélin mun framkvæma þrjár lotur:

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

Inntak 2

1 1
1
1 1

Úttak 2

-1