A12093. Balls and Pockets

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):

0 1 2 3 4 5 6 7 8 9 ... After opening and closing the pockets, balls 1, 3 and 4 disappear:

0 2 5 6 7 8 9 ... After moving all the balls to the left, the configuration looks like this:

0 2 5 6 7 8 9 10 11 12 ... Another filtering repetition results in the following:

0 5 8 9 10 11 12 13 14 15 ... 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.