CF555D.Case of a Top Secret

Andrewid the Android is a galaxy-famous detective. Now he is busy with a top secret case, the details of which are not subject to disclosure.

However, he needs help conducting one of the investigative experiment. There are n pegs put on a plane, they are numbered from 1 to n, the coordinates of the i-th of them are (x__i, 0). Then, we tie to the bottom of one of the pegs a weight on a tight rope of length l (thus, its coordinates will be equal to (x__i,  - l), where i is the number of the used peg). Then the weight is pushed to the right, so that it starts to rotate counterclockwise. At the same time, if the weight during rotation touches some of the other pegs, it then begins to rotate around that peg. Suppose that each peg itself is very thin and does not affect the rope length while weight is rotating around it.

More formally, if at some moment the segment of the rope contains one or more pegs in addition to the peg around which the weight is rotating, the weight will then rotate around the farthermost one of them on a shorter segment of a rope. In particular, if the segment of the rope touches some peg by its endpoint, it is considered that the weight starts to rotate around that peg on a segment of the rope of length 0.

At some moment the weight will begin to rotate around some peg, without affecting the rest of the pegs. Andrewid interested in determining the number of this peg.

Andrewid prepared m queries containing initial conditions for pushing the weight, help him to determine for each of them, around what peg the weight will eventually rotate.

安卓侦探安德鲁伊德是银河系闻名的侦探。目前，他正忙于一桩绝密案件，案件细节恕不透露。

然而，他需要协助开展一项调查实验。平面上放置了 $n$ 个钉子，编号从 $1$ 到 $n$，其中第 $i$ 个钉子的坐标为 $(x_i,\,0)$。接着，我们取其中某一个钉子（设其编号为 $i$），在其正下方用一根长度为 $l$ 的绷紧绳子悬挂一个重物（此时重物坐标为 $(x_i,\,-l)$）。随后，将该重物向右推动，使其开始逆时针旋转。在此过程中，若重物在旋转途中触碰到其他某个钉子，则它将立即改绕该钉子旋转。假设每个钉子本身极细，在重物绕其旋转时不会影响绳长。

更严格地讲：在某一时刻，若当前绳段（即从当前旋转中心钉子到重物的线段）上除当前旋转中心外还包含一个或多个其他钉子，则重物将立即改绕其中距离当前重物位置最近的那个钉子旋转（即：以该钉子为新中心，绳长缩短为该钉子到重物当前位置的距离）；等价地，这等同于改绕该绳段上离当前重物最远的那个钉子旋转（因绳段端点即重物位置，故“离重物最远”即“离旋转中心最近”——但题意实际指：在当前绳段上，选取所有被穿过的钉子中，离当前旋转中心最远者作为新中心，新绳长即为该钉子到重物的距离）。特别地，若当前绳段的端点（即重物位置）恰好与某个钉子重合，则视为重物开始绕该钉子以绳长 $0$ 旋转。

最终，重物将稳定地绕某个钉子持续旋转，且不再与其他钉子发生相互作用。安德鲁伊德希望确定该最终旋转所围绕的钉子编号。

安德鲁伊德准备了 $m$ 个查询，每个查询给出一次实验的初始条件（即初始悬挂钉子编号及绳长 $l$），请你帮助他判断：对每个查询，重物最终将绕哪一个钉子旋转？

The first line contains integers n and m (1 ≤ n, m ≤ 2·105) — the number of pegs and queries.

The next line contains n integers _x_1, _x_2, ..., x__n ( - 109 ≤ x__i ≤ 109) — the coordinates of the pegs. It is guaranteed that the coordinates of all the pegs are distinct integers.

Next m lines contain the descriptions of the queries of pushing the weight, each consists of two integers a__i (1 ≤ a__i ≤ n) and l__i (1 ≤ l__i ≤ 109) — the number of the starting peg and the length of the rope.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 2 \cdot 10^5$）—— 分别表示钉子的数量和查询次数。

第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$（$-10^9 \leq x_i \leq 10^9$）—— 表示各钉子的坐标。保证所有钉子的坐标均为互不相同的整数。

接下来 $m$ 行，每行描述一次将重物推下的查询，每行包含两个整数 $a_i$（$1 \leq a_i \leq n$）和 $l_i$（$1 \leq l_i \leq 10^9$）—— 分别表示起始钉子的编号和绳子的长度。

Print m lines, the i-th line should contain the number of the peg around which the weight will eventually rotate after the i-th push.

输出 m 行，其中第 i 行应包含在第 i 次推动后，重物最终绕其旋转的钉子的编号。

Picture to the first sample test:

Picture to the second sample test:

Note that in the last query weight starts to rotate around the peg 1 attached to a rope segment of length 0.

第一个样例测试的示意图：

第二个样例测试的示意图：

注意：在最后一次查询中，重物开始绕固定于长度为 0 的绳段上的桩 1 旋转。