← 返回题目列表

Codeforces · 1060/G

G. 球和口袋

中文机器翻译题面 查看原题

有一条带有无限数量的单元格的条带。单元格编号从 $$$0$$$ 开始。最初,单元格 $$$i$$$ 包含一个编号为 $$$i$$$ 的球。

单元格 $$$a_1、\ldots、a_n$$$ 处有 $$$n$$$ 口袋。每个单元最多包含一个口袋。

过滤是以下操作序列:

- $$$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$$$ 处的球的编号是多少?”

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ - 分别是口袋数和问题数 ($$$1 \leq n, m \leq 10^5$$$)。

以下行包含 $$$n$$$ 整数 $$$a_1, \ldots, a_n$$$ - 包含口袋的单元格数量 ($$$0 \leq a_1 < \ldots < a_n \leq 10^9$$$)。

以下 $$$m$$$ 行描述了问题。这些行的第 $$$i$$$ 包含两个整数 $$$x_i$$$ 和 $$$k_i$$$ ($$$0 \leq x_i, k_i \leq 10^9$$$)。

输出

按输入中给出的顺序打印 $$$m$$$ 数字 — 问题的答案。

示例

输入 #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