Представьте себе бесконечный пруд, спроецированный на числовую прямую. В пруду есть $$$n$$$ камней, пронумерованных от $$$1$$$ до $$$n$$$. $$$i$$$-й камень находится в целой координате $$$a_i$$$. Координаты камней попарно различны. Камни пронумерованы в порядке увеличения координаты, поэтому $$$a_1 < a_2 < \dots < a_n$$$.
Лягушка-робот сидит на камне номер $$$s$$$. Лягушку можно запрограммировать. У нее есть встроенный параметр базовой длины прыжка $$$d$$$. Также есть настройка для интервала длины прыжка. Если интервал длины прыжка выставляется на некоторое целое значение $$$k$$$, то лягушка может прыгать с некоторого камня на любой другой камень на расстоянии от $$$d - k$$$ до $$$d + k$$$ включительно в любом направлении. Расстояние между двумя камнями — это модуль разности между их координатами.
Вам поручили задачу реализовать новую функцию для лягушки. По двум заданным целым числам $$$i$$$ и $$$k$$$ определить, может ли лягушка достичь камня номер $$$i$$$ с камня номер $$$s$$$, осуществив последовательность прыжков с интервалом длины прыжка установленным на $$$k$$$. Последовательность может быть сколь угодно длинной или пустой.
Вам будет предоставлено $$$q$$$ тестов для данной функции, $$$j$$$-й набор состоит из двух целых чисел $$$i$$$ и $$$k$$$. Выведите «Yes», если $$$i$$$-й камень достижим и «No» в противном случае.
Вы можете выводить «YES» и «NO» в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).
В первой строке записаны четыре целых числа $$$n$$$, $$$q$$$, $$$s$$$ и $$$d$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$; $$$1 \le s \le n$$$; $$$1 \le d \le 10^6$$$) — количество камней, количество тестов, начальный камень и базовая длина прыжка.
Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — координаты камней. Координаты камней попарно различны. Камни пронумерованы в порядке увеличения координаты, поэтому $$$a_1 < a_2 < \dots < a_n$$$.
В каждой из следующих $$$q$$$ строк записаны два целых числа $$$i$$$ и $$$k$$$ ($$$1 \le i \le n$$$; $$$1 \le k \le 10^6$$$) — параметры теста.
На каждый тест выведите ответ. Если существует такая последовательность прыжков с камня номер $$$s$$$ до камня номер $$$i$$$ с интервалом длины прыжка установленным на $$$k$$$, то выведите «Yes». В противном случае выведите «No».
7 4 4 5 1 5 10 13 20 22 28 4 1 7 2 7 3 3 2
Yes No Yes Yes
10 8 6 11 1 2 4 7 8 9 11 13 19 20 2 13 5 8 8 1 6 15 1 15 2 7 7 6 8 9
Yes Yes No Yes Yes Yes Yes Yes
6 9 6 6 1 2 4 9 18 19 2 17 1 18 5 4 2 11 5 17 6 8 4 3 3 3 6 6
Yes Yes Yes Yes Yes Yes No No Yes
4 1 1 10 1 8 10 19 2 1
Yes
Пояснение к первому примеру:
В первом тесте финальный камень тот же, что и начальный, поэтому не надо прыгать, чтобы его достичь.
Во втором тесте лягушка может прыгать на любую длину в отрезке $$$[5 - 2; 5 + 2]$$$. Поэтому она может достичь камня номер $$$5$$$ (прыжком на $$$7$$$ направо) и камня номер $$$3$$$ (прыжком на $$$3$$$ налево). С камня номер $$$3$$$ она может достичь камня номер $$$2$$$ (прыжком на $$$5$$$ налево). С камня номер $$$2$$$ она может достичь камня номер $$$1$$$ (прыжком на $$$4$$$ налево). Однако, нет способа достичь камня номер $$$7$$$.
В третьем тесте лягушка может прыгать на любую длину в отрезке $$$[5 - 3; 5 + 3]$$$. Поэтому она может достичь камня номер $$$7$$$, прыгнув сначала на камень номер $$$5$$$, а с него на $$$7$$$.
Четвертый тест показан в описании ко второму тесту.
Название |
---|