Problem G
Stikl

Number tiles eftir geralt, Pixabay

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

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