Hide

Problem G
Stikl

Languages en is

/problems/stikl/file/statement/en/img-0001.jpg

Number tiles by geralt, Pixabay

You really like playing games with your friend. A current favorite of yours is the game Stikl. During the setup of the game $n$ numbered tiles are shuffled and placed in a line. The rules of the game are simple. Both players start on a random tile. They then take turns rollling dice and make the corresponding number of moves. One move consists of a player moving from their initial tile to the first tile on their right that does not have a lower number than the initial tile. If no such tile exists, the player wins. The only difficult part of the game is figuring out where a player’s piece piece ends after a certain number of moves.

Input

The first line of the input consists of two integers $n$, the number of tiles, where $1 \leq n \leq 10^5$, and $q$, the number of queries, where $1 \leq q \leq 10^5$. The second line of the input consists of $n$ space separated integers, corresponding to the numbers on the tiles. Then follow $q$ queries, one on each lines. The $j$-th query contains two integers $s_ j$, the number of the tile on which the player starts, where $1 \leq s_ j \leq n$, and $d_ j$, the number of steps the player takes, where $1 \leq d_ j \leq 10^5$.

Output

For each query, print a single line containing the index of the tile the player ends on if they start at the $s_ j$-th tile and make $d_ j$ moves. If preforming the prescribed number of moves would cause the player to win, then print “leik lokid”.

Scoring

Group	Points	Constraints
1	42	$n, q \leq 100$
2	26	$s$ is always $1$
3	32	No further constraints

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

Problem GStikl

Input

Output

Scoring

Problem G
Stikl