Kattis

# Stikl

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 rolling dice and make the corresponding number of moves. One move consists of moving from your inital tile to the first tile to your 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 this game is figuring out where your piece ends after a certain number of moves.

## Input

The first line of the input consist of two integers $1 \leq n \leq 10^5$ and $1 \leq q \leq 10^5$. The second line of the input consists of $n$ integers, $1 \leq a_ i \leq 10^9$. Theses integers correspond to the numbers on the tiles. Then follow $q$ queries, one on each line, containing two integers, $1 \leq s_ j \leq n$ and $1 \leq d_ j \leq 10^5$.

## Output

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

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

Sample Input 2 Sample Output 2
5 5
1 1 1 1 1
1 1
1 3
1 5
2 4
2 5

2
4
leik lokid
leik lokid
leik lokid