E. Игра с картами
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в очень интересную карточную игру. На каждой карте в этой игре написано одно целое число. На протяжении игры у Боба в каждой из двух рук находится ровно одна карта. Изначально Боб держит в левой руке карту с числом 0, а в правой руке — также карту с числом 0.

Алиса делает $$$n$$$ ходов. На ходу с номером $$$i$$$ она предлагает Бобу карту с числом $$$k_i$$$, а также 4 числа $$$a_i$$$, $$$b_i$$$, $$$c_i$$$, $$$d_i$$$. Боб выбирает, в какую руку он хочет взять новую карту, после чего выбрасывает карту из этой руки и берет в эту руку новую карту Алисы. После этого Алиса проверяет карты Боба. А именно, пусть он в левой руке держит карту $$$x$$$, а в правой — карту $$$y$$$. Тогда должно выполняться $$$a_i \le x \le b_i$$$ и $$$c_i \le y \le d_i$$$, иначе игра немедленно заканчивается.

Боб заранее знает все числа $$$k_i$$$, $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ и $$$d_i$$$. Помогите ему выбрать для каждого хода, в левую или правую руку ему следует класть очередную карту, чтобы в итоге все условия Алисы были выполнены.

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

В первой строке вводятся два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 100\,000$$$, $$$2 \le m \le 10^9$$$) — количество ходов в игре и максимально возможное число, записанное на карте.

Далее следует описание $$$n$$$ ходов. Каждое описание состоит из трех строк.

В первой строке описания $$$i$$$-го запроса вводится целое число $$$k_i$$$ ($$$0 \le k_i \le m$$$) — число, записанное на новой карте.

Во второй строке описания $$$i$$$-го запроса вводятся два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$0 \le a_i \le b_i \le m$$$) — минимальное и максимальное допустимые значения для карты из левой руки после хода $$$i$$$.

В третьей строке описания $$$i$$$-го запроса вводятся два целых числа $$$c_i$$$ и $$$d_i$$$ ($$$0 \le c_i \le d_i \le m$$$) — минимальное и максимальное допустимые значения для карты из правой руки после хода $$$i$$$.

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

Если Боб не сможет удовлетворить все условия Алисы, выведите «No». Иначе в первой строке выведите «Yes», а затем в следующей строке выведите $$$n$$$ чисел — в какую руку Бобу следует класть очередную карту: если Бобу нужно взять карту в левую руку, выведите 0, иначе выведите 1. В случае, если у Боба существует несколько способов удовлетворить условиям Алисы, выведите любой из них.

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

Тесты к этой задаче состоят из 6 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп.

Доп. ограничения
ГруппаБаллы$$$n$$$$$$m$$$Необх. группыКомментарий
00–––Тесты из условия.
115$$$n \le 15$$$$$$m \le 100$$$0
215$$$n \le 100$$$$$$m \le 100$$$0, 1
315$$$n \le 1000$$$$$$m \le 1000$$$0 – 2
415$$$n \le 10\,000$$$$$$m \le 10\,000$$$0 – 3
520–––$$$a_i = 0$$$ и $$$c_i = 0$$$ при любом $$$i$$$
620––0 – 5
Примеры
Входные данные
2 10
3
0 3
0 2
2
0 4
0 2
Выходные данные
Yes
0 1
Входные данные
2 10
3
0 3
0 2
2
3 4
0 1
Выходные данные
No
Входные данные
5 10
3
0 3
0 3
7
4 7
1 3
2
2 3
3 7
8
1 8
1 8
6
1 6
7 10
Выходные данные
Yes
1 0 0 1 0
Примечание

В первом примере из условия Боб может взять карту из первого хода в левую руку. После этого у него в руках будут карты $$$3$$$ и $$$0$$$, которые соответствуют ограничениям ($$$0 \le 3 \le 3$$$ для левой руки и $$$0 \le 0 \le 2$$$ для правой).

Карту из второго хода Боб может взять в правую руку, после чего в его руках будут карты $$$3$$$ и $$$2$$$, которые соответствуют ограничениям ($$$0 \le 3 \le 4$$$ для левой руки и $$$0 \le 2 \le 2$$$ для правой руки). Таким образом, Боб может удовлетворить всем ограничениям Алисы, и в этом случае ответ «Yes».