← 返回题目列表

Codeforces · 555/D

D. 绝密案件

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

Android 安德鲁是一位银河系著名的侦探。现在他正忙着处理一件绝密案件,具体细节不便透露。

然而,他需要帮助进行其中一项调查实验。平面上放有 n 个钉子,编号从 1 到 n,第 i 个钉子的坐标为 (xi, 0)。然后,我们在其中一个钉子的底部绑上一根长度为 l 的紧绳上的重物(因此,其坐标将等于 (xi, - l),其中 i 是所使用的钉子的编号)。然后将重物推向右侧,使其开始逆时针旋转。同时,如果旋转过程中的重物接触到其他一些钉子,它就会开始围绕该钉子旋转。假设每个钉子本身非常细,并且当重物围绕其旋转时不会影响绳子的长度。

更正式地说,如果在某个时刻,除了重物围绕其旋转的栓钉之外,绳索的该段还包含一个或多个栓钉,则重物将围绕绳索较短一段上最远的一个栓钉旋转。特别是,如果绳索段的端点接触到某个栓钉,则认为重量开始围绕长度为 0 的绳索段上的该栓钉旋转。

在某个时刻,重物将开始围绕某个钉子旋转,而不影响其余的钉子。安德鲁德有兴趣确定这个挂钩的数量。

Andrewid 准备了 m 个查询,其中包含推动重物的初始条件,帮助他确定每个查询中重物最终将围绕哪个挂钩旋转。

输入

第一行包含整数 n 和 m (1 ≤ n, m ≤ 2·105) — 挂钩和查询的数量。

下一行包含 n 个整数 x1, x2, ..., xn (- 109 ≤ xi ≤ 109) — 钉子的坐标。保证所有钉子的坐标都是不同的整数。

接下来 m 行包含推重查询的描述,每行由两个整数 ai (1 ≤ ai ≤ n) 和 li (1 ≤ li ≤ 109) — 起始桩的数量和绳子的长度组成。

输出

打印 m 行,第 i 行应包含在第 i 次推动后重物最终将围绕其旋转的挂钩编号。

示例

输入 #1

3 2
0 3 5
2 3
1 8

输出 #1

3
2

输入 #2

4 4
1 5 7 15
1 4
2 15
3 16
1 28

输出 #2

2
4
3
1

注意

第一个样本测试图片:

第二个样本测试图片:

请注意,在最后一个查询中,重量开始围绕连接到长度为 0 的绳段的栓 1 旋转。