Balls and Pockets

题意翻译

### 题目翻译 给出一个无限长的序列 $p_0,p_1,p_2,\ldots$，初始 $p_i=i$。 给出 $n$ 个互不相同的整数 $a_1,a_2,\ldots,a_n$，可以对序列 $p$ 做以下操作若干次： - 将序列 $p$ 的第 $a_1,a_2,\ldots,a_n$ 项从序列 $p$ 中删掉，然后将剩余的数字按照原来在序列 $p$ 中的顺序重新排列作为新的序列 $p$。 举个栗子：初始序列为 `0 1 2 3 4 5 6 7 8 9...`，$a = \{1,3,4\}$，那么 - 经过 1 次操作后序列变为 `0 2 5 6 7 8 9 10 11 12...`； - 经过 2 次操作后序列变为 `0 5 8 9 10 11 12 13 14 15...`…… 给出 $m$ 组询问，每组询问给出两个整数 $x,k$，询问进行 $k$ 次操作后的序列 $p$ 中 $p_x$ 的值。 ### 输入格式 第一行两个整数 $m,n(1 \leq m,n \leq 10^5)$， 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n(0 \leq a_1 < \ldots < a_n \leq 10^9)$。 接下来 $m$ 行每行两个整数 $x_i,k_i(0 \leq x_i,k_i \leq 10^9)$ 描述一组询问。 ### 输出格式 $m$ 行，每行一个整数表示对应询问答案。

题目描述

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.

输入输出样例

输入样例 #1

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

输出样例 #1

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