有一条带有无限数量的单元格的条带。单元格编号从 $$$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