#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <chrono>
#include <random>
#include <string>
#include <numeric>
#include <complex>
#include <tuple>
#include <utility>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;

#define pb push_back
#define ppp pop_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define stie std::tie
#define vec vector
#define forn(i, l, r) for (int i=l; i<=r; i++)
#define forb(i, r, l) for (int i=r; i>=l; i--)
#define emp empty
#define beg begin
#define ins insert
#define cle clear
#define era erase
#define que queue
#define pque priority_queue
#define mset multiset
#define deq deque
#define sta stack
#define con const
#define rsz resize
#define ass assign
#define lowb lower_bound
#define uppb upper_bound

template <class T> void mini(T& a, T b) { a = min(a, b); }
template <class T> void maxi(T& a, T b) { a = max(a, b); }
template <class T> T gcd(T a, T b) { return b == 0 ? a : gcd(b, a % b); }
template <class T1, class T2>
ostream& operator<<(ostream& os, pair<T1, T2> const& a) { return os << "[" << a.first << ", " << a.second << "]"; }
template <class Ch, class Tr, class Container>
basic_ostream<Ch, Tr>& operator<<(basic_ostream<Ch, Tr>& os, Container const& a) { os << "{ "; for (auto& i : a) os << i << " "; return os << "}"; }
template <class T> void out(T a) { cout << a << endl; }
template <class T, class... Args> void out(T a, Args... args) { cout << a << " "; out(args...); }
template <class T> void out(std::initializer_list<T> a) { for (auto i : a) { cout << i << " "; } cout << endl; }
template <class T> void out(vector<vector<T>> a) { for (vector<T> i : a) out(i); }
template <class T> void out_(T a[], int l, int r) { for (int i = l; i <= r; i++) cout << a[i] << " "; cout << endl; }
void out() { cout << "OK" << endl; }
template <class T> void sort(vector<T>& a) { sort(a.begin(), a.end()); }
template <class T> void rever(vector<T>& a) { reverse(a.begin(), a.end()); }
template <class T> void uniq(vector<T>& a) { sort(a); a.erase(unique(a.begin(), a.end()), a.end()); }
template <class T> vector<T> set_int(vector<T> a, vector<T> b) { sort(a); sort(b); vector<T> res;
set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(res)); return res; }
clock_t start_time; void start_timer() { start_time = clock(); }
double get_time() { return (double)(clock() - start_time) / CLOCKS_PER_SEC; }
#if __SIZEOF_INT128__ >= 16
typedef __int128 LL;
istream& operator>>(istream& in, __int128& a) { int64_t b; in >> b; a = b; return in; }
ostream& operator<<(ostream& out, const __int128 a) {
    unsigned __int128 b = a < 0 ? -a : a; char buf[128]; char* c = end(buf); do { --c; *c = "0123456789"[b % 10]; b /= 10; } while (b);
    if (a < 0) { --c; *c = '-'; } int64_t len = end(buf) - c; out.rdbuf()->sputn(c, len); return out;
}
#endif

// solve the problem or die trying
// do something, stay focused
// look for stupid bugs
// guess, slow, stress
// the solution is always simple

con int N = 1e5 + 5;
con int K = 1 << 17;

struct seg_max {
    int t[2 * K];
    void upd(int v, int x) {
        v += K;
        t[v] = x;
        v /= 2;
        while (v) {
            t[v] = max(t[v + v], t[v + v + 1]);
            v /= 2;
        }
    }
    int get(int l, int r) {
        l += K;
        r += K;
        int res = -1;
        while (l <= r) {
            if (l % 2 == 1) maxi(res, t[l++]);
            if (r % 2 == 0) maxi(res, t[r--]);
            l /= 2;
            r /= 2;
        }
        return res;
    }
};

struct seg_min {
    int t[2 * K];
    void upd(int v, int x) {
        v += K;
        t[v] = x;
        v /= 2;
        while (v) {
            t[v] = min(t[v + v], t[v + v + 1]);
            v /= 2;
        }
    }
    int get(int l, int r) {
        l += K;
        r += K;
        int res = 1e9;
        while (l <= r) {
            if (l % 2 == 1) mini(res, t[l++]);
            if (r % 2 == 0) mini(res, t[r--]);
            l /= 2;
            r /= 2;
        }
        return res;
    }
};

int dp[2][N];
int L[2][N];
int R[2][N];
int a[N];
int last[2];
int par[2][N];
int up[2][N];
int ans[N];
seg_max lef;
seg_min rig;
int suf[2][N];

bool bet(int x, int y, int z) {
    return x <= y && y <= z;
}

void Solve() {
    int n, m;
    cin >> n >> m;
    forn(i, 1, n) {
        cin >> a[i];
        cin >> L[0][i] >> R[0][i];
        cin >> L[1][i] >> R[1][i];
    }
    forn(s, 0, 1) {
        if (bet(L[s][n], a[n], R[s][n])) {
            dp[s][n] = 1;
            par[s][n] = n + 1;
            last[s] = n;
        }
        else {
            last[s] = n + 4;
        }
    }
    forn(s, 0, 1) {
        forn(i, 0, n) {
            lef.upd(i, L[s][i]);
            rig.upd(i, R[s][i]);
        }
        forn(i, 0, n) {
            int l = i - 1;
            int r = n;
            while (l < r) {
                int m = (l + r) / 2 + 1;
                if (l < 0) {
                    m = (l + 1 + r + 1) / 2;
                }
                bool ok = bet(lef.get(i, m), a[i], rig.get(i, m));
                if (ok) l = m;
                else r = m - 1;
            }
            up[s][i] = l;
        }
    }
    forn(s, 0, 1) {
        forb(i, n + 1, 0) {
            suf[s][i] = suf[s][i + 1];
            if (up[s][i] >= i) {
                suf[s][i]++;
            }
        }
    }
    forb(i, n - 1, 0) {
        forn(s, 0, 1) {
            if (up[s][i] >= last[s ^ 1] && suf[s ^ 1][i + 1] - suf[s ^ 1][last[s ^ 1] + 1] == last[s ^ 1] - (i + 1) + 1) {
                dp[s][i] = 1;
                par[s][i] = last[s ^ 1];
            }
        }
        forn(s, 0, 1) {
            if (dp[s][i]) {
                last[s] = i;
            }
        }
    }
    if (dp[0][0] == 0 && dp[1][0] == 0) {
        out("No");
        return;
    }
    int s = 0;
    int id = 0;
    if (!dp[0][0]) {
        s = 1;
        id = 0;
    }
    while (id <= n) {
        ans[id] = s;
        int x = par[s][id];
        forn(i, id + 1, x - 1) {
            ans[i] = s ^ 1;
        }
        id = x;
        s ^= 1;
    }
    out("Yes");
    forn(i, 1, n) {
        cout << ans[i] << " ";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
    freopen("usr/share/man/man1/input.txt", "r", stdin);
#endif
    start_timer();
    Solve();
    return 0;
}

### Prompt

Create a solution in Cpp for the following 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 

### Response

```cpp
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <chrono>
#include <random>
#include <string>
#include <numeric>
#include <complex>
#include <tuple>
#include <utility>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;

#define pb push_back
#define ppp pop_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define stie std::tie
#define vec vector
#define forn(i, l, r) for (int i=l; i<=r; i++)
#define forb(i, r, l) for (int i=r; i>=l; i--)
#define emp empty
#define beg begin
#define ins insert
#define cle clear
#define era erase
#define que queue
#define pque priority_queue
#define mset multiset
#define deq deque
#define sta stack
#define con const
#define rsz resize
#define ass assign
#define lowb lower_bound
#define uppb upper_bound

template <class T> void mini(T& a, T b) { a = min(a, b); }
template <class T> void maxi(T& a, T b) { a = max(a, b); }
template <class T> T gcd(T a, T b) { return b == 0 ? a : gcd(b, a % b); }
template <class T1, class T2>
ostream& operator<<(ostream& os, pair<T1, T2> const& a) { return os << "[" << a.first << ", " << a.second << "]"; }
template <class Ch, class Tr, class Container>
basic_ostream<Ch, Tr>& operator<<(basic_ostream<Ch, Tr>& os, Container const& a) { os << "{ "; for (auto& i : a) os << i << " "; return os << "}"; }
template <class T> void out(T a) { cout << a << endl; }
template <class T, class... Args> void out(T a, Args... args) { cout << a << " "; out(args...); }
template <class T> void out(std::initializer_list<T> a) { for (auto i : a) { cout << i << " "; } cout << endl; }
template <class T> void out(vector<vector<T>> a) { for (vector<T> i : a) out(i); }
template <class T> void out_(T a[], int l, int r) { for (int i = l; i <= r; i++) cout << a[i] << " "; cout << endl; }
void out() { cout << "OK" << endl; }
template <class T> void sort(vector<T>& a) { sort(a.begin(), a.end()); }
template <class T> void rever(vector<T>& a) { reverse(a.begin(), a.end()); }
template <class T> void uniq(vector<T>& a) { sort(a); a.erase(unique(a.begin(), a.end()), a.end()); }
template <class T> vector<T> set_int(vector<T> a, vector<T> b) { sort(a); sort(b); vector<T> res;
set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(res)); return res; }
clock_t start_time; void start_timer() { start_time = clock(); }
double get_time() { return (double)(clock() - start_time) / CLOCKS_PER_SEC; }
#if __SIZEOF_INT128__ >= 16
typedef __int128 LL;
istream& operator>>(istream& in, __int128& a) { int64_t b; in >> b; a = b; return in; }
ostream& operator<<(ostream& out, const __int128 a) {
    unsigned __int128 b = a < 0 ? -a : a; char buf[128]; char* c = end(buf); do { --c; *c = "0123456789"[b % 10]; b /= 10; } while (b);
    if (a < 0) { --c; *c = '-'; } int64_t len = end(buf) - c; out.rdbuf()->sputn(c, len); return out;
}
#endif

// solve the problem or die trying
// do something, stay focused
// look for stupid bugs
// guess, slow, stress
// the solution is always simple

con int N = 1e5 + 5;
con int K = 1 << 17;

struct seg_max {
    int t[2 * K];
    void upd(int v, int x) {
        v += K;
        t[v] = x;
        v /= 2;
        while (v) {
            t[v] = max(t[v + v], t[v + v + 1]);
            v /= 2;
        }
    }
    int get(int l, int r) {
        l += K;
        r += K;
        int res = -1;
        while (l <= r) {
            if (l % 2 == 1) maxi(res, t[l++]);
            if (r % 2 == 0) maxi(res, t[r--]);
            l /= 2;
            r /= 2;
        }
        return res;
    }
};

struct seg_min {
    int t[2 * K];
    void upd(int v, int x) {
        v += K;
        t[v] = x;
        v /= 2;
        while (v) {
            t[v] = min(t[v + v], t[v + v + 1]);
            v /= 2;
        }
    }
    int get(int l, int r) {
        l += K;
        r += K;
        int res = 1e9;
        while (l <= r) {
            if (l % 2 == 1) mini(res, t[l++]);
            if (r % 2 == 0) mini(res, t[r--]);
            l /= 2;
            r /= 2;
        }
        return res;
    }
};

int dp[2][N];
int L[2][N];
int R[2][N];
int a[N];
int last[2];
int par[2][N];
int up[2][N];
int ans[N];
seg_max lef;
seg_min rig;
int suf[2][N];

bool bet(int x, int y, int z) {
    return x <= y && y <= z;
}

void Solve() {
    int n, m;
    cin >> n >> m;
    forn(i, 1, n) {
        cin >> a[i];
        cin >> L[0][i] >> R[0][i];
        cin >> L[1][i] >> R[1][i];
    }
    forn(s, 0, 1) {
        if (bet(L[s][n], a[n], R[s][n])) {
            dp[s][n] = 1;
            par[s][n] = n + 1;
            last[s] = n;
        }
        else {
            last[s] = n + 4;
        }
    }
    forn(s, 0, 1) {
        forn(i, 0, n) {
            lef.upd(i, L[s][i]);
            rig.upd(i, R[s][i]);
        }
        forn(i, 0, n) {
            int l = i - 1;
            int r = n;
            while (l < r) {
                int m = (l + r) / 2 + 1;
                if (l < 0) {
                    m = (l + 1 + r + 1) / 2;
                }
                bool ok = bet(lef.get(i, m), a[i], rig.get(i, m));
                if (ok) l = m;
                else r = m - 1;
            }
            up[s][i] = l;
        }
    }
    forn(s, 0, 1) {
        forb(i, n + 1, 0) {
            suf[s][i] = suf[s][i + 1];
            if (up[s][i] >= i) {
                suf[s][i]++;
            }
        }
    }
    forb(i, n - 1, 0) {
        forn(s, 0, 1) {
            if (up[s][i] >= last[s ^ 1] && suf[s ^ 1][i + 1] - suf[s ^ 1][last[s ^ 1] + 1] == last[s ^ 1] - (i + 1) + 1) {
                dp[s][i] = 1;
                par[s][i] = last[s ^ 1];
            }
        }
        forn(s, 0, 1) {
            if (dp[s][i]) {
                last[s] = i;
            }
        }
    }
    if (dp[0][0] == 0 && dp[1][0] == 0) {
        out("No");
        return;
    }
    int s = 0;
    int id = 0;
    if (!dp[0][0]) {
        s = 1;
        id = 0;
    }
    while (id <= n) {
        ans[id] = s;
        int x = par[s][id];
        forn(i, id + 1, x - 1) {
            ans[i] = s ^ 1;
        }
        id = x;
        s ^= 1;
    }
    out("Yes");
    forn(i, 1, n) {
        cout << ans[i] << " ";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
    freopen("usr/share/man/man1/input.txt", "r", stdin);
#endif
    start_timer();
    Solve();
    return 0;
}

```