Антон играет в игру 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 | — | — |
46 7 2 42 64 71 63 71 44 65 7 1 41 72 61 73 51 78 100 10 5049 5148 5058 6068 7078 8077 7987 8986 887 8 5 71 81 81 81 81 81 81 7
Yes No Yes No
Первый тестовый случай в примере совпадает с уровнем на картинке.