F. Попрыгунчик
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Представьте себе бесконечный пруд, спроецированный на числовую прямую. В пруду есть $$$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$$$.

Четвертый тест показан в описании ко второму тесту.