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

Initially, Bob holds one card with number 0 in the left hand and one in the right hand. In the i-th question, Alice asks Bob to replace a card in the left or right hand with a card with number k_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 x, and on the right card be y. Then after the i-th swap the following conditions must be satisfied: a_{l, i} ≤ x ≤ b_{l, i}, and a_{r, i} ≤ y ≤ b_{r,i}.

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

Input

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

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

The first line of the description of the i-th query contains a single integer k_i (0 ≤ k_i ≤ m) — the number on a new card.

The second line of the description of the i-th query contains two integers a_{l, i} and b_{l, i} (0 ≤ a_{l, i} ≤ b_{l, i} ≤ m) — the minimum and maximum values of the card at the left hand after the replacement.

The third line of the description of the i-th query contains two integers a_{r, i} and b_{r,i} (0 ≤ a_{r, i} ≤ b_{r,i} ≤ 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 n queries, then at the second line print n numbers: a way to satisfy all requirements. If in i-th query Bob needs to replace the card in the left hand, print 0, otherwise print 1. If there are multiple answers, print any.

Examples

Input


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


Output


Yes
0 1 

Input


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


Output


No

Input


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


Output


Yes
1 0 0 1 0 

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Iterator;
import java.util.Timer;
import java.util.TreeSet;
import java.util.TimerTask;
import java.util.Comparator;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author sarthakmanna
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        EGameWithCards solver = new EGameWithCards();
        solver.solve(1, in, out);
        out.close();
    }

    static class EGameWithCards {
        int Q;
        int M;
        int[] C;
        int[][] L;
        int[][] R;
        TreeSet<int[]> vis;

        public void solve(int testNumber, FastReader in, PrintWriter out) {
            int i, j, k;
            Timer timer = new Timer();
            TimerTask task = new TimerTask() {

                public void run() {
                    System.out.println("No");
                    System.exit(0);
                }
            };
            timer.schedule(task, 2100);

            vis = new TreeSet<>(new Comparator<int[]>() {

                public int compare(int[] a, int[] b) {
                    for (int i = 0; i < 3; ++i) if (a[i] != b[i]) return Integer.compare(a[i], b[i]);
                    return 0;
                }
            });


            Q = in.nextInt();
            M = in.nextInt();
            C = new int[Q];
            L = new int[Q][2];
            R = new int[Q][2];
            for (i = 0; i < Q; ++i) {
                C[i] = in.nextInt();
                L[i] = in.getIntArray(2);
                R[i] = in.getIntArray(2);
            }

            myArrayListInteger ans = new myArrayListInteger(Q);
            while (ans.size() < Q) ans.add(-7);
            if (recurse(0, 0, 0, ans)) {
                out.println("Yes");
                out.println(ans);
            } else {
                out.println("No");
            }
            timer.cancel();
        }

        boolean recurse(int idx, int l, int r, myArrayListInteger list) {
            int[] key = new int[]{idx, l, r};
            if (idx == C.length) {
                return true;
            } else if (vis.contains(key)) {
                return false;
            }

            if (L[idx][0] <= C[idx] && C[idx] <= L[idx][1] && R[idx][0] <= r && r <= R[idx][1] &&
                    recurse(idx + 1, C[idx], r, list)) {
                list.set(idx, 0);
                return true;
            }
            if (L[idx][0] <= l && l <= L[idx][1] && R[idx][0] <= C[idx] && C[idx] <= R[idx][1] &&
                    recurse(idx + 1, l, C[idx], list)) {
                list.set(idx, 1);
                return true;
            }

            vis.add(key);
            return false;
        }

    }

    static class FastReader {
        static final int BUFSIZE = 1 << 20;
        static byte[] buf;
        static int index;
        static int total;
        static InputStream in;

        public FastReader(InputStream is) {
            try {
                in = is;
                buf = new byte[BUFSIZE];
            } catch (Exception e) {
            }
        }

        private int scan() {
            try {
                if (index >= total) {
                    index = 0;
                    total = in.read(buf);
                    if (total <= 0)
                        return -1;
                }
                return buf[index++];
            } catch (Exception | Error e) {
                System.err.println(e.getMessage());
                return 13 / 0;
            }
        }

        public int nextInt() {
            int c, val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+')
                c = scan();
            for (; c >= '0' && c <= '9'; c = scan())
                val = (val << 3) + (val << 1) + (c & 15);
            return neg ? -val : val;
        }

        public int[] getIntArray(int size) {
            int[] ar = new int[size];
            for (int i = 0; i < size; ++i) ar[i] = nextInt();
            return ar;
        }

    }

    static class myArrayListInteger implements Iterable<Integer> {
        private int len;
        private int[] A;
        int itrInd;

        public myArrayListInteger(int initialLength) {
            A = new int[Math.max(1, initialLength)];
            len = 0;
        }

        public myArrayListInteger(myArrayListInteger src) {
            A = new int[src.A.length];
            System.arraycopy(src.A, 0, A, 0, src.len);
            len = src.len;
        }

        public void add(int ele) {
            if (len == A.length) {
                int[] newAr = new int[A.length << 1];
                System.arraycopy(A, 0, newAr, 0, len);
                A = newAr;
            }
            A[len++] = ele;
        }

        public void set(int ind, int ele) {
            if (ind >= len) throw new ArrayIndexOutOfBoundsException(ind);
            else if (ind < 0) ind += size();
            A[ind] = ele;
        }

        public int get(int ind) {
            if (ind >= len) throw new ArrayIndexOutOfBoundsException(ind);
            else if (ind < 0) ind += size();
            return A[ind];
        }

        public int size() {
            return len;
        }

        public Iterator<Integer> iterator() {
            itrInd = 0;
            Iterator<Integer> iterator = new Iterator<Integer>() {

                public boolean hasNext() {
                    return itrInd < size();
                }


                public Integer next() {
                    return get(itrInd++);
                }
            };
            return iterator;
        }

        public myArrayListInteger clone() {
            return new myArrayListInteger(this);
        }

        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < len; i++) sb.append(A[i]).append(" ");
            return sb.toString().trim();
        }

    }
}