#P1539E. Game with Cards

    ID: 2073 Type: RemoteJudge 2000ms 256MiB Tried: 0 Accepted: 0 Difficulty: 9 Uploaded By: Tags>binary searchconstructive algorithmsdata structuresdpgreedyimplementation*2500

Game with Cards

Description

The Alice's computer is broken, so she can't play her favorite card game now. To help Alice, Bob wants to answer nn her questions.

Initially, Bob holds one card with number 00 in the left hand and one in the right hand. In the ii-th question, Alice asks Bob to replace a card in the left or right hand with a card with number kik_i (Bob chooses which of two cards he changes, Bob must replace exactly one card).

After this action, Alice wants the numbers on the left and right cards to belong to given segments (segments for left and right cards can be different). Formally, let the number on the left card be xx, and on the right card be yy. Then after the ii-th swap the following conditions must be satisfied: al,ixbl,ia_{l, i} \le x \le b_{l, i}, and ar,iybr,ia_{r, i} \le y \le b_{r,i}.

Please determine if Bob can answer all requests. If it is possible, find a way to do it.

The first line contains two integers nn and mm (2n1000002 \le n \le 100\,000, 2m1092 \le m \le 10^9) — the number of questions and the maximum possible value on the card.

Then nn queries are described. Every description contains 3 lines.

The first line of the description of the ii-th query contains a single integer kik_i (0kim0 \le k_i \le m) — the number on a new card.

The second line of the description of the ii-th query contains two integers al,ia_{l, i} and bl,ib_{l, i} (0al,ibl,im0 \le a_{l, i} \le b_{l, i} \le m) — the minimum and maximum values of the card at the left hand after the replacement.

The third line of the description of the ii-th query contains two integers ar,ia_{r, i} and br,ib_{r,i} (0ar,ibr,im0 \le a_{r, i} \le b_{r,i} \le m) — the minimum and maximum values of the card at the right hand after the replacement.

At the first line, print "Yes", if Bob can answer all queries, and "No" otherwise.

If Bob can answer all nn queries, then at the second line print nn numbers: a way to satisfy all requirements. If in ii-th query Bob needs to replace the card in the left hand, print 00, otherwise print 11. If there are multiple answers, print any.

Input

The first line contains two integers nn and mm (2n1000002 \le n \le 100\,000, 2m1092 \le m \le 10^9) — the number of questions and the maximum possible value on the card.

Then nn queries are described. Every description contains 3 lines.

The first line of the description of the ii-th query contains a single integer kik_i (0kim0 \le k_i \le m) — the number on a new card.

The second line of the description of the ii-th query contains two integers al,ia_{l, i} and bl,ib_{l, i} (0al,ibl,im0 \le a_{l, i} \le b_{l, i} \le m) — the minimum and maximum values of the card at the left hand after the replacement.

The third line of the description of the ii-th query contains two integers ar,ia_{r, i} and br,ib_{r,i} (0ar,ibr,im0 \le a_{r, i} \le b_{r,i} \le m) — the minimum and maximum values of the card at the right hand after the replacement.

Output

At the first line, print "Yes", if Bob can answer all queries, and "No" otherwise.

If Bob can answer all nn queries, then at the second line print nn numbers: a way to satisfy all requirements. If in ii-th query Bob needs to replace the card in the left hand, print 00, otherwise print 11. If there are multiple answers, print any.

Sample Input 1

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

Sample Output 1

Yes
0 1

Sample Input 2

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

Sample Output 2

No

Sample Input 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

Sample Output 3

Yes
1 0 0 1 0