Қоймаға $1$-ден $n$-ге дейін нөмірленген $n$ сәлемдеме жаңа ғана келіп түсті. Олар $a_1, \dots, a_n$ ретімен келді, ал біз оларды $1, 2, \dots, n$ ретімен тұратындай етіп сұрыптағымыз келеді.

Қоймадағы сұрыптау машинасы кезең-кезеңімен жұмыс істейді. Әр кезең $a_1, \dots, a_n$ сәлемдемелер қатарын қабылдап, келесідей әрекет етеді: алдымен бірінші $a_1$ сәлемдемесі жаңа қатарға қойылады. Содан кейін $i = 2, \dots, n$ үшін әрбір $a_i$ сәлемдемесі үшін, егер $a_i$ жаңа қатардағы соңғы (ең оң жақтағы) сәлемдемеден үлкен болса, машина оны қатардың соңына қояды. Әйтпесе, оны қатардың басына қояды.

Егер жаңа қатар сұрыпталмаған болса, ол сұрыптау машинасының келесі кезеңіне кіріс ретінде беріледі.

«$t$ кезеңнен кейін $b$-ші орында қاي сәлемдеме тұр» деген сұраныстарға жауап беру арқылы машинаның ойдағыдай жұмыс істейтінін тексеруге көмектесетін программа жазыңыз.

Кіріс деректер

Кірістің бірінші жолында сәйкесінше сәлемдемелер санын және сұраныстар санын білдіретін екі бүтін сан $n$ және $q$ ($1 \le n, q \le 5 \cdot 10^5$) берілген.

Екінші жолда сәлемдемелердің бастапқы ретін білдіретін $n$ бүтін саннан тұратын $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$) тізбегі берілген.

Келесі $q$ жолда сұраныстар берілген; $i$-ші жолда $i$-ші сұранысты білдіретін екі бүтін сан $t_i$ және $b_i$ ($0 \le t_i \le 10^9$, $1 \le b_i \le n$) бар.

Шығыс деректер

Дәл $q$ жол шығарыңыз. $i$-ші жолда $i$-ші сұраныстың жауабы болуы тиіс.

Егер машина $t_i$ кезеңнен аз орындаса, $-1$ шығарыңыз. Әйтпесе, $t_i$ кезең орындалғаннан кейін сол жақтан санағанда $b_i$ орында қай сәлемдеме тұрғанын шығарыңыз.

Мысалдар

Кіріс 1

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

Шығыс 1

4
2
-1
5

Ескертпе 1

Машина үш кезеңді орындайды:

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

Кіріс 2

1 1
1
1 1

Шығыс 2

-1