CF1060G.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 \lt 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?"

存在一条无限长的格子带，格子从 $0$ 开始编号。初始时，格子 $i$ 中放置一个编号为 $i$ 的球。

有 $n$ 个口袋，分别位于格子 $a_1, \ldots, a_n$ 处。每个格子至多包含一个口袋。

过滤操作（Filtering）定义为以下一系列步骤：

• 所有位于格子 $a_1, \ldots, a_n$ 的口袋同时打开，使得当前位于这些格子中的球立即消失；随后口袋关闭。
• 对每个从 $0$ 到 $\infty$ 的格子 $i$：若格子 $i$ 中含有一个球，则将该球移动到编号最小的空闲格子 $j$（即尚未被任何球占据的格子）；若不存在满足 $j < i$ 的空闲格子，则该球保留在格子 $i$ 中。

注意：每次过滤操作后，每个格子仍恰好包含一个球。

例如，设口袋位于格子 $1$、$3$ 和 $4$ 处。初始球的分布如下（下划线标出含口袋的格子）：

0 1 2 3 4 5 6 7 8 9 ...

口袋打开并关闭后，编号为 $1$、$3$、$4$ 的球消失：

0 2 5 6 7 8 9 ...

将所有球向左移动至最近的空闲格子后，配置变为：

0 2 5 6 7 8 9 10 11 12 ...

再执行一次过滤操作，得到：

0 5 8 9 10 11 12 13 14 15 ...

你需要回答 $m$ 个询问。第 $i$ 个询问为：“经过 $k_i$ 次过滤操作后，位于格子 $x_i$ 的球的编号是多少？”

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 \lt \ldots \lt 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$).

第一行包含两个整数 $n$ 和 $m$ —— 分别表示口袋的数量和问题的数量（$1 \leq n, m \leq 10^5$）。

接下来的一行包含 $n$ 个整数 $a_1, \ldots, a_n$ —— 表示包含口袋的单元格编号（$0 \leq a_1 \lt \ldots \lt a_n \leq 10^9$）。

接下来的 $m$ 行描述了各个问题。其中第 $i$ 行包含两个整数 $x_i$ 和 $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.

输出 $m$ 个数字——即对各个询问的回答，顺序与输入中给出的顺序一致。