Case of a Top Secret

平面上有 $n$ 个钉子，从 $1$ 到 $n$ 编号，第 $i$ 个钉子的坐标是 $(x_i,0)$。 把一个长度为 $L$，带重物的绳子系到第 $i$ 个钉子上，即重物所在的坐标是$(x_i,-L)$。然后将重物向右推，绳子开始逆时针旋转。 如果旋转的过程中绳子碰到其它的钉子，就会绕着那个钉子旋转。 如果绳子碰到多个钉子，那么它会绕着离刚才的钉子的最远的那个钉子转。（参考图示） 如果绳子的末端碰到了一个钉子，那么绳子也会绕着那个钉子、以长度为 $0$ 的在转。 每个钉子都很细，重物绕着它旋转时，不影响到绳子的长度。 经过一段时间之后，重物就会一直绕着某个钉子转。 现在有 $m$ 个查询，每个查询给出初始的绳子长度以及挂在哪个钉子下旋转，请找出重物最终会绕哪个钉子旋转。 ### 输入格式 第 $1$ 行两个整数 $n,m$，分别表示钉子数和绳子重物数。 第 $2$ 行 $n$ 个整数 $x_i$，表示钉子的横坐标。 接下来 $m$ 行，每行两个整数 $a_i，l_i$，表示绳子绑在第 $a_i$ 个钉子上，绳长 $l_i$。 ### 输出格式 $m$ 行，每行一个整数，表示第 $i$ 根绳子最终绕着转的钉子编号。 ### 范围 $1\le n,m\le 2\times10^5$ $1\le a_i\le n$ $-10^9\le x_i\le 10^9$ $1\le l_i\le 10^9$ 翻译修改自[题解](https://www.luogu.com.cn/blog/SJYAKIOI/solution-cf555d)

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.

The first line contains integers $ n $ and $ m $ ( $ 1<=n,m<=2·10^{5} $ ) — the number of pegs and queries. The next line contains $ n $ integers $ x_{1},x_{2},...,x_{n} $ ( $ -10^{9}<=x_{i}<=10^{9} $ ) — 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}<=10^{9} $ ) — the number of the starting peg and the length of the rope.

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.

3 2
0 3 5
2 3
1 8

3
2

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

2
4
3
1

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.