Flappy Bird
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Антон играет в игру Flappy Bird. Антон играет за птичку, которой нужно пролететь по уровню слева-направо. Высота уровня равна $$$h$$$, то есть есть $$$h$$$ различных высот, на которых может находиться птичка. Высоты пронумерованы числами от $$$1$$$ до $$$h$$$ от самой низкой до самой высокой. Уровень состоит из $$$n$$$ столбцов, расположенных друг за другом слева направо, и пронумерованных числами от $$$1$$$ до $$$n$$$. В $$$i$$$-м столбце есть две трубы, одна расположена снизу, другая сверху. Нижняя труба занимает все высоты от $$$1$$$ до $$$l_i$$$ включительно, а верхняя занимает все высоты от $$$r_i$$$ до $$$h$$$ включительно. Это значит, что в $$$i$$$-м столбце птичка может находиться на высотах от $$$l_i + 1$$$ до $$$r_i - 1$$$ включительно.

Птичка летит следующим образом: изначально она находится в первом столбце на высоте $$$s$$$ ($$$l_1 < s < r_1$$$), а затем $$$n-1$$$ раз перемещается в следующий столбец. Перед перемещением в следующий столбец игрок может нажать кнопку прыжка, тогда птичка поднимется на $$$k$$$ вверх, т.е. если птичка в текущем столбце находилась на высоте $$$x$$$, тогда в следующем столбце она окажется на высоте $$$x+k$$$. Если же игрок не нажмет кнопку прыжка, то птичка снизится на одну единицу высоты, т.е. если она была на высоте $$$x$$$, то окажется на высоте $$$x - 1$$$. Заметим, что вертикальное перемещение птички происходит между столбцами. Это значит, что внутри одного столбца птичка проходит только по одной высоте и никак не перемещается горизонтально. Единственное ограничение для ее положения — ее высота в $$$i$$$-м столбце должна быть от $$$l_i + 1$$$ до $$$r_i - 1$$$ включительно.

Отметим также, что птичка никогда не может опускаться ниже первой и подниматься выше $$$h$$$-й высоты.

Уровень будет пройден, если птичка дойдет до $$$n$$$-го столбца.

Рассмотрим пример уровня (это первый тестовый случай в тесте из условия):

Здесь горизонтальные линии обозначают высоты, на которых может находиться птичка, они пронумерованы от $$$1$$$ до $$$7$$$ (т. е. $$$h=7$$$). Изначально птичка находится на высоте $$$s=4$$$, высота ее прыжка равна $$$k=2$$$. В данном примере существует ровно один способ пройти уровень, и он изображен на рисунке. В каждом столбце птичка нарисована на той высоте, на которой она должна находиться в этом столбце.

Помогите Антону и узнайте, может ли он пройти уровень (т. е. может ли птичка двигаться так, чтобы добраться до $$$n$$$-го столбца).

Входные данные

В первой строке дано одно целое число $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — количество наборов входных данных. Далее следуют описания каждого из наборов входных данных.

В первой строке каждого набора входных данных дано четыре целых числа $$$n$$$, $$$h$$$, $$$k$$$ и $$$s$$$ ($$$2 \leq n \leq 100\,000$$$, $$$4 \leq h \leq 10^9$$$, $$$1 \leq k \leq h - 3$$$, $$$2 \leq s \leq h - 1$$$) — количество столбцов, высота уровня, высота прыжка и стартовая высота.

В следующих $$$n$$$ строках описываются уровни. В $$$i$$$-й из них дано два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \leq l_i < r_i \leq h$$$, $$$l_i + 2 \le r_i$$$) — высоты нижней и верхней трубы в $$$i$$$-м столбце. Гарантируется, что $$$l_1 < s < r_1$$$.

Пусть $$$N$$$ равное сумме $$$n$$$ по всем наборам входных данных. Гарантируется, что $$$N \leq 500\,000$$$.

Выходные данные

Выведите $$$t$$$ строк. В $$$i$$$-й строке выведите Yes если Антон может пройти уровень из $$$i$$$-го набора входных данных, иначе выведите No.

Система оценки

Всего в этой задаче $$$20$$$ тестов (не считая теста из условия). Оценка потестовая, каждый из тестов, кроме теста из условия, оценивается в $$$5$$$ баллов. На некоторые из тестов наложены дополнительные ограничения, указанные в таблице.

ТестыДополнительные ограниченияКомментарий
1Тест из условия
2, 3, 4$$$r_i = l_i + 2$$$
5, 6, 7$$$n \leq 10$$$
8, 9, 10$$$h \leq 100$$$
11, 12, 13$$$r_i - l_i \leq 100$$$
14, 15, 16$$$n \leq 1000, N \leq 30\,000$$$
17, 18$$$k=1$$$
19, 20, 21

Пример

Входные данные
4
6 7 2 4
2 6
4 7
1 6
3 7
1 4
4 6
5 7 1 4
1 7
2 6
1 7
3 5
1 7
8 100 10 50
49 51
48 50
58 60
68 70
78 80
77 79
87 89
86 88
7 8 5 7
1 8
1 8
1 8
1 8
1 8
1 8
1 7
Выходные данные
Yes
No
Yes
No

Примечание

Первый тестовый случай в примере совпадает с уровнем на картинке.