Hide

Problem F
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