Problem Description

Tin is a renowned magician, and one of his classic tricks involves shuffling cards.

Tin prepares a deck of $n$ cards (guaranteed to be an even number), numbered from $1$ to $n$. Initially, the cards are shuffled and face down on the table. During the shuffling process, at any moment, a spectator can ask Tin what the $t$-th card from the bottom is, and Tin will immediately provide the correct answer.

In fact, Tin accomplishes this trick by following these steps:

1. He memorizes the initial order of the $n$ cards.
2. He then shuffles using the following technique:
3. He picks up the top $\frac{n}{2}$ cards with his right hand and the bottom $\frac{n}{2}$ cards with his left hand, both facing the table.
4. Using his memory, he compares the bottom cards of both hands and places the card with the smaller number down. This process is repeated until one hand is empty.
5. He then places all the remaining cards from the hand that still has cards.

Write a program to simulate Tin's magic trick.

Input Format

The first line contains two integers $N$ and $Q$.

The next line contains $N$ integers $p_i$, describing the deck from bottom to top.

The following $Q$ lines each contain a query with two integers $t$ and $i$, asking for the number of the $i$-th card from the bottom after $t$ shuffles.

Output Format

For each query, output the answer.

Sample Input and Output

Sample Input #1

6 3
1 5 6 2 3 4
1 2
0 4
1 5

Sample Output #1

2
2
5

Sample Input #2

6 6
2 1 5 4 6 3
0 1
1 1
0 3
1 3
0 6
10 6

Sample Output #2

2
2
5
4
3
3

Sample Input #3

10 10
7 5 2 9 10 8 4 3 6 1
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10

Sample Output #3

2
3
6
1
7
5
8
4
9
10

Notes/Hints

Sample 3 Explanation

Data Constraints

For all data, $1 \le N \le 2 \times 10^5$, $N$ is even, $1 \le Q \le 10^6$, $0 \le t \le 10^9$, $p$ is a permutation of $1$ to $n$, $1 \le i \le N$.

见题面 Input 部分

见题面 Output 部分