Codeforces Round 310 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

implementation

math

*2500

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Case of a Top Secret

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAndrewid 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.

Input

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.

Output

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.

Examples

Input

3 2

0 3 5

2 3

1 8

Output

3

2

Input

4 4

1 5 7 15

1 4

2 15

3 16

1 28

Output

2

4

3

1

Note

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/24/2024 21:07:15 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|