← 返回题目列表

Codeforces · 1539/E

E. 纸牌游戏

中文机器翻译题面 查看原题

Alice的电脑坏了,所以她现在不能玩她最喜欢的纸牌游戏。为了帮助爱丽丝,鲍勃想回答 $$$n$$$ 她的问题。

最初,Bob 左手拿着一张数字为 $$$0$$$ 的牌,右手拿着一张。在第 $$$i$$$ 问题中,Alice 要求 Bob 将左手或右手的一张牌替换为编号为 $$$k_i$$$ 的牌(Bob 选择更换两张牌中的哪一张,Bob 必须替换一张牌)。

执行此操作后,Alice 希望左右卡上的数字属于给定的段(左右卡的段可以不同)。形式上,让左卡上的数字为$$$x$$$,右卡上的数字为$$$y$$$。然后,在第 $$$i$$$ 次交换之后,必须满足以下条件:$$$a_{l, i} \le x \le b_{l, i}$$$ 和 $$$a_{r, i} \le y \le b_{r,i}$$$。

请确定 Bob 是否可以回答所有请求。如果可以的话,想办法去做。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 100\,000$$$, $$$2 \le m \le 10^9$$$) - 问题数量和卡片上的最大可能值。

然后描述 $$$n$$$ 查询。每个描述包含 3 行。

第 $$$i$$$ 查询的描述的第一行包含一个整数 $$$k_i$$$ ($$$0 \le k_i \le m$$$) — 新卡上的号码。

第 $$$i$$$ 查询的描述的第二行包含两个整数 $$$a_{l, i}$$$ 和 $$$b_{l, i}$$$ ($$$0 \le a_{l, i} \le b_{l, i} \le m$$$)——替换后左手牌的最小值和最大值。

第 $$$i$$$ 查询的描述第三行包含两个整数 $$$a_{r, i}$$$ 和 $$$b_{r,i}$$$ ($$$0 \le a_{r, i} \le b_{r,i} \le m$$$)——替换后右手牌的最小值和最大值。

输出

在第一行,如果 Bob 可以回答所有查询,则打印“Yes”,否则打印“No”。

如果 Bob 可以回答所有 $$$n$$$ 查询,则在第二行打印 $$$n$$$ 数字:满足所有要求的一种方法。如果在第 $$$i$$$ 查询中 Bob 需要更换左手的卡,则打印 $$$0$$$,否则打印 $$$1$$$。如果有多个答案,请打印其中一个。

示例

输入 #1

2 10
3
0 3
0 2
2
0 4
0 2

输出 #1

Yes
0 1

输入 #2

2 10
3
0 3
0 2
2
3 4
0 1

输出 #2

No

输入 #3

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

输出 #3

Yes
1 0 0 1 0