Balls and Pockets
Description
There is a strip with an infinite number of cells. Cells are numbered starting with $0$. Initially the cell $i$ contains a ball with the number $i$.
There are $n$ pockets located at cells $a_1, \ldots, a_n$. Each cell contains at most one pocket.
Filtering is the following sequence of operations:
- All pockets at cells $a_1, \ldots, a_n$ open simultaneously, which makes balls currently located at those cells disappear. After the balls disappear, the pockets close again.
- For each cell $i$ from $0$ to $\infty$, if the cell $i$ contains a ball, we move that ball to the free cell $j$ with the lowest number. If there is no free cell $j < i$, the ball stays at the cell $i$.
Note that after each filtering operation each cell will still contain exactly one ball.
For example, let the cells $1$, $3$ and $4$ contain pockets. The initial configuration of balls is shown below (underscores display the cells with pockets):
After opening and closing the pockets, balls 1, 3 and 4 disappear:
After moving all the balls to the left, the configuration looks like this:
Another filtering repetition results in the following:
You have to answer $m$ questions. The $i$-th of these questions is "what is the number of the ball located at the cell $x_i$ after $k_i$ repetitions of the filtering operation?"
The first line contains two integers $n$ and $m$ — the number of pockets and questions respectively ($1 \leq n, m \leq 10^5$).
The following line contains $n$ integers $a_1, \ldots, a_n$ — the numbers of cells containing pockets ($0 \leq a_1 < \ldots < a_n \leq 10^9$).
The following $m$ lines describe questions. The $i$-th of these lines contains two integers $x_i$ and $k_i$ ($0 \leq x_i, k_i \leq 10^9$).
Print $m$ numbers — answers to the questions, in the same order as given in the input.
Input
The first line contains two integers $n$ and $m$ — the number of pockets and questions respectively ($1 \leq n, m \leq 10^5$).
The following line contains $n$ integers $a_1, \ldots, a_n$ — the numbers of cells containing pockets ($0 \leq a_1 < \ldots < a_n \leq 10^9$).
The following $m$ lines describe questions. The $i$-th of these lines contains two integers $x_i$ and $k_i$ ($0 \leq x_i, k_i \leq 10^9$).
Output
Print $m$ numbers — answers to the questions, in the same order as given in the input.
Samples
3 15
1 3 4
0 0
1 0
2 0
3 0
4 0
0 1
1 1
2 1
3 1
4 1
0 2
1 2
2 2
3 2
4 2
0
1
2
3
4
0
2
5
6
7
0
5
8
9
10