Hide

Problem G
Stikl

Languages en is
/problems/stikl/file/statement/is/img-0001.jpg
Number tiles eftir geralt, Pixabay
Þú elskar að spila leiki með vini þínum. Um þessar mundir er uppháldið ykkar leikurinn Stikl. Til að byrja með eru $n$ reitir settir í línu, og tala af handahófi skrifuð á hvern þeirra. Reglur leiksins eru einfaldar. Báðir leikmenn byrja á reit af handahófi. Þeir skiptast svo á að kasta tening og framkvæma svo fjölda skrefa samkvæmt því. Hvert skref virkar þannig að leikmaðurinn færir sig á fyrsta reitinn til hægri sem hefur ekki lægra númer en reiturinn sem hann er nú þegar á. Það erfiðasta við þennan leik er að finna út hvar leikmaðurinn endar eftir ákveðinn fjölda af skrefum.

Inntak

Fyrsta lína inniheldur tvær heiltölur $n$ og $q$ ($1 \leq n, q \leq 10^5$), fjöldi reita og fjöldi fyrirspurna. Önnur lína inniheldur $n$ heiltölur $a_1,a_2,\ldots ,a_ n$ ($1 \leq a_ i \leq 10^9$) sem tákna tölurnar á reitunum frá vinstri til hægri. Svo fylgja $q$ fyrirspurnir, hver á línu sem inniheldur tvær heiltölur $s$ og $d$ ($1 \leq s \leq n$, $1 \leq d \leq 10^5$), númerið á reitnum sem leikmaður byrjar á og fjöldi skrefa sem hann framkvæmir.

Úttak

Fyrir hverja fyrirspurn skrifið út eina línu með númeri reitsins sem leikmaðurinn endar á, ef hann byrjar á reit $s$ og framkvæmir $d$ skref. Ef leikmaðurinn myndi hoppa út fyrir enda reitanna, skrifið þá ,,leik lokid“ í þeirri fyrirspurn.

Stigagjöf

Hópur

Stig

Takmarkanir

1

42

$n, q \leq 100$

2

26

$s$ er alltaf $1$

3

32

Engar frekari takmarkanir

Sample Input 1 Sample Output 1
16 11
1 9 5 13 3 11 7 15 2 10 6 14 4 12 8 16
1 1
1 2
1 3
1 4
1 5
3 1
3 4
5 1
9 3
11 3
16 1
2
4
8
16
leik lokid
4
leik lokid
6
16
leik lokid
leik lokid