| Codeforces Round 310 (Div. 1) |
|---|
| Закончено |
Андроид Андреид — известный на всю галактику детектив. Сейчас он занят особо секретным делом, детали которого не подлежат разглашению.
Однако ему требуется помощь при проведении одного следственного эксперимента. На плоскости ставятся n колышков, пронумерованных от 1 до n, координаты i-го из них — (xi, 0). Затем за один из колышков снизу привязывают груз на натянутой веревке длины l (таким образом, его координаты будут равны (xi, - l), где i — номер использованного колышка), после чего этот груз толкают вправо, так, что он начинает вращаться против часовой стрелки. При этом, если груз в процессе вращения цепляется за какой-то из колышков, то он начинает вращаться уже вокруг этого колышка. Можно предположить, что каждый колышек в отдельности достаточно тонкий, и не влияет на длину верёвки груза, который вокруг него вращается.
Более формально, если в некоторый момент времени отрезок верёвки содержит один или несколько колышков кроме того, вокруг которого сейчас вращается груз, то далее груз будет вращаться вокруг наиболее удалённого из них на более коротком отрезке верёвки. В частности, если отрезок верёвки задевает своим концом некоторый колышек, то считается, что груз начинает вращаться вокруг этого колышка на отрезке верёвки длины 0.
Рано или поздно груз начнёт вращаться вокруг некоторого колышка, не задевая остальные колышки. Андреид заинтересован в определении номера этого колышка.
Андреид подготовил 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-го запуска.
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
Иллюстрация к первому тесту из условия:
Иллюстрация ко второму тесту из условия:
Обратите внимание, что в последнем запуске груз в итоге начинает вращаться вокруг первого колышка на отрезке верёвки длины 0.
