#include <bits/stdc++.h>

using namespace std;

static struct FastInput {
  static constexpr int BUF_SIZE = 1 << 20;
  char buf[BUF_SIZE];
  size_t chars_read = 0;
  size_t buf_pos = 0;
  FILE *in = stdin;
  char cur = 0;
 
  inline char get_char() {
    if (buf_pos >= chars_read) {
      chars_read = fread(buf, 1, BUF_SIZE, in);
      buf_pos = 0;
      buf[0] = (chars_read == 0 ? -1 : buf[0]);
    }
    return cur = buf[buf_pos++];
  }
 
  inline void tie(int) {}
 
  inline explicit operator bool() {
    return cur != -1;
  }
 
  inline static bool is_blank(char c) {
    return c <= ' ';
  }
 
  inline bool skip_blanks() {
    while (is_blank(cur) && cur != -1) {
      get_char();
    }
    return cur != -1;
  }
 
  inline FastInput& operator>>(char& c) {
    skip_blanks();
    c = cur;
    return *this;
  }
  
  inline FastInput& operator>>(string& s) {
    if (skip_blanks()) {
      s.clear();
      do {
        s += cur;
      } while (!is_blank(get_char()));
    }
    return *this;
  }
 
  template <typename T>
  inline FastInput& read_integer(T& n) {
    // unsafe, doesn't check that characters are actually digits
    n = 0;
    if (skip_blanks()) {
      int sign = +1;
      if (cur == '-') {
        sign = -1;
        get_char();
      }
      do {
        n += n + (n << 3) + cur - '0';
      } while (!is_blank(get_char()));
      n *= sign;
    }
    return *this;
  }
 
  template <typename T>
  inline typename enable_if<is_integral<T>::value, FastInput&>::type operator>>(T& n) {
    return read_integer(n);
  }
  
  #if !defined(_WIN32) || defined(_WIN64)
  inline FastInput& operator>>(__int128& n) {
    return read_integer(n);
  }
  #endif
 
  template <typename T>
  inline typename enable_if<is_floating_point<T>::value, FastInput&>::type operator>>(T& n) {
    // not sure if really fast, for compatibility only
    n = 0;
    if (skip_blanks()) {
      string s;
      (*this) >> s;
      sscanf(s.c_str(), "%lf", &n);
    }
    return *this;
  }
} fast_input;
 
#define cin fast_input

static struct FastOutput {
  static constexpr int BUF_SIZE = 1 << 20;
  char buf[BUF_SIZE];
  size_t buf_pos = 0;
  static constexpr int TMP_SIZE = 1 << 20;
  char tmp[TMP_SIZE];
  FILE *out = stdout;
 
  inline void put_char(char c) {
    buf[buf_pos++] = c;
    if (buf_pos == BUF_SIZE) {
      fwrite(buf, 1, buf_pos, out);
      buf_pos = 0;
    }
  }
 
  ~FastOutput() {
    fwrite(buf, 1, buf_pos, out);
  }
 
  inline FastOutput& operator<<(char c) {
    put_char(c);
    return *this;
  }
 
  inline FastOutput& operator<<(const char* s) {
    while (*s) {
      put_char(*s++);
    }
    return *this;
  }
 
  inline FastOutput& operator<<(const string& s) {
    for (int i = 0; i < (int) s.size(); i++) {
      put_char(s[i]);
    }
    return *this;
  }
 
  template <typename T>
  inline char* integer_to_string(T n) {
    // beware of TMP_SIZE
    char* p = tmp + TMP_SIZE - 1;
    if (n == 0) {
      *--p = '0';
    } else {
      bool is_negative = false;
      if (n < 0) {
        is_negative = true;
        n = -n;
      }
      while (n > 0) {
        *--p = (char) ('0' + n % 10);
        n /= 10;
      }
      if (is_negative) {
        *--p = '-';
      }
    }
    return p;
  }
 
  template <typename T>
  inline typename enable_if<is_integral<T>::value, char*>::type stringify(T n) {
    return integer_to_string(n);
  }
 
  #if !defined(_WIN32) || defined(_WIN64)
  inline char* stringify(__int128 n) {
    return integer_to_string(n);
  }
  #endif
 
  template <typename T>
  inline typename enable_if<is_floating_point<T>::value, char*>::type stringify(T n) {
    sprintf(tmp, "%.17f", n);
    return tmp;
  }
 
  template <typename T>
  inline FastOutput& operator<<(const T& n) {
    auto p = stringify(n);
    for (; *p != 0; p++) {
      put_char(*p);
    }
    return *this;
  }
} fast_output;

// here puts define
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#define rint register int
#define rll register ll 
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fors(i, a, b) for (int i = (a); i <= (b); ++i)
#define _fors(i, a, b) for (int i = (a); i >= (b); --i)
#define cyc(m) fors(rqtwqtqwt, 1, m)
#define mp(a, b) make_pair(a, b)
#define mt(a, b, c) make_tuple(a, b, c)
#define mem(A, b) memset(A, b, sizeof(A))
#define all(X) (X).begin(), (X).end()
#define y0 gawgfawgawg
#define y1 sdfyseyegeh
#define pb push_back
#define eb emplace_back
#define cout fast_output
#define endl '\n'
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

int start_time;

const int _ = 1e5 + 5;

int n, m;
int k[_];
int l[_][2], r[_][2];
int las[_][2];
set<vector<int> > s[2];

void write(int cur, int kin) {
  if (cur == 0) return ;
  write(las[cur][kin], kin ^ 1);
  fors(i, las[cur][kin] + 1, cur) cout << kin << " \n"[i == n];
  return ;
}

bool in(int x, int id, int i) {
  return x >= l[id][i] && x <= r[id][i];
}

void solve() {
  cin >> n >> m;
  fors(i, 1, n) {
    cin >> k[i];
    cin >> l[i][0] >> r[i][0];
    cin >> l[i][1] >> r[i][1];
  }
  if (in(0, 1, 0) && in(k[1], 1, 1)) s[0].insert({0, 0});
  if (in(0, 1, 1) && in(k[1], 1, 0)) s[1].insert({0, 0});
  fors(i, 2, n) {
    int emp0 = s[0].empty(), emp1 = s[1].empty();
    if (!emp0) s[1].insert({k[i - 1], i - 1});
    if (!emp1) s[0].insert({k[i - 1], i - 1});
    if (in(k[i], i, 0)) {
      while (!s[1].empty() && !in((*s[1].begin())[0], i, 1)) s[1].erase(s[1].begin());
      while (!s[1].empty() && !in((*s[1].rbegin())[0], i, 1)) s[1].erase(s[1].lower_bound(*s[1].rbegin()));
    }
    else s[1].clear();
    if (in(k[i], i, 1)) {
      while (!s[0].empty() && !in((*s[0].begin())[0], i, 0)) s[0].erase(s[0].begin());
      while (!s[0].empty() && !in((*s[0].rbegin())[0], i, 0)) s[0].erase(s[0].lower_bound(*s[0].rbegin()));  
    }
    else s[0].clear();
    if (!s[0].empty()) las[i][1] = (*s[0].begin())[1];
    if (!s[1].empty()) las[i][0] = (*s[1].begin())[1]; 
  }
  if (s[0].empty() && s[1].empty()) { no; return ; }
  yes;
  if (!s[0].empty()) write(n, 1);
  else write(n, 0);
  return ;
}

signed main() {
  #ifdef Sakuyalove 
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif 
  ios::sync_with_stdio(false);
  cin.tie(0);
  start_time = clock();
  int T = 1;
  // cin >> T;
  while (T--) {
    solve();
  }

  #ifdef Sakuyalove
    cout << "time = " << clock() - start_time << endl;
  #endif

  return 0;
}
### Prompt

Your task is to create a CPP solution to 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 <bits/stdc++.h>

using namespace std;

static struct FastInput {
  static constexpr int BUF_SIZE = 1 << 20;
  char buf[BUF_SIZE];
  size_t chars_read = 0;
  size_t buf_pos = 0;
  FILE *in = stdin;
  char cur = 0;
 
  inline char get_char() {
    if (buf_pos >= chars_read) {
      chars_read = fread(buf, 1, BUF_SIZE, in);
      buf_pos = 0;
      buf[0] = (chars_read == 0 ? -1 : buf[0]);
    }
    return cur = buf[buf_pos++];
  }
 
  inline void tie(int) {}
 
  inline explicit operator bool() {
    return cur != -1;
  }
 
  inline static bool is_blank(char c) {
    return c <= ' ';
  }
 
  inline bool skip_blanks() {
    while (is_blank(cur) && cur != -1) {
      get_char();
    }
    return cur != -1;
  }
 
  inline FastInput& operator>>(char& c) {
    skip_blanks();
    c = cur;
    return *this;
  }
  
  inline FastInput& operator>>(string& s) {
    if (skip_blanks()) {
      s.clear();
      do {
        s += cur;
      } while (!is_blank(get_char()));
    }
    return *this;
  }
 
  template <typename T>
  inline FastInput& read_integer(T& n) {
    // unsafe, doesn't check that characters are actually digits
    n = 0;
    if (skip_blanks()) {
      int sign = +1;
      if (cur == '-') {
        sign = -1;
        get_char();
      }
      do {
        n += n + (n << 3) + cur - '0';
      } while (!is_blank(get_char()));
      n *= sign;
    }
    return *this;
  }
 
  template <typename T>
  inline typename enable_if<is_integral<T>::value, FastInput&>::type operator>>(T& n) {
    return read_integer(n);
  }
  
  #if !defined(_WIN32) || defined(_WIN64)
  inline FastInput& operator>>(__int128& n) {
    return read_integer(n);
  }
  #endif
 
  template <typename T>
  inline typename enable_if<is_floating_point<T>::value, FastInput&>::type operator>>(T& n) {
    // not sure if really fast, for compatibility only
    n = 0;
    if (skip_blanks()) {
      string s;
      (*this) >> s;
      sscanf(s.c_str(), "%lf", &n);
    }
    return *this;
  }
} fast_input;
 
#define cin fast_input

static struct FastOutput {
  static constexpr int BUF_SIZE = 1 << 20;
  char buf[BUF_SIZE];
  size_t buf_pos = 0;
  static constexpr int TMP_SIZE = 1 << 20;
  char tmp[TMP_SIZE];
  FILE *out = stdout;
 
  inline void put_char(char c) {
    buf[buf_pos++] = c;
    if (buf_pos == BUF_SIZE) {
      fwrite(buf, 1, buf_pos, out);
      buf_pos = 0;
    }
  }
 
  ~FastOutput() {
    fwrite(buf, 1, buf_pos, out);
  }
 
  inline FastOutput& operator<<(char c) {
    put_char(c);
    return *this;
  }
 
  inline FastOutput& operator<<(const char* s) {
    while (*s) {
      put_char(*s++);
    }
    return *this;
  }
 
  inline FastOutput& operator<<(const string& s) {
    for (int i = 0; i < (int) s.size(); i++) {
      put_char(s[i]);
    }
    return *this;
  }
 
  template <typename T>
  inline char* integer_to_string(T n) {
    // beware of TMP_SIZE
    char* p = tmp + TMP_SIZE - 1;
    if (n == 0) {
      *--p = '0';
    } else {
      bool is_negative = false;
      if (n < 0) {
        is_negative = true;
        n = -n;
      }
      while (n > 0) {
        *--p = (char) ('0' + n % 10);
        n /= 10;
      }
      if (is_negative) {
        *--p = '-';
      }
    }
    return p;
  }
 
  template <typename T>
  inline typename enable_if<is_integral<T>::value, char*>::type stringify(T n) {
    return integer_to_string(n);
  }
 
  #if !defined(_WIN32) || defined(_WIN64)
  inline char* stringify(__int128 n) {
    return integer_to_string(n);
  }
  #endif
 
  template <typename T>
  inline typename enable_if<is_floating_point<T>::value, char*>::type stringify(T n) {
    sprintf(tmp, "%.17f", n);
    return tmp;
  }
 
  template <typename T>
  inline FastOutput& operator<<(const T& n) {
    auto p = stringify(n);
    for (; *p != 0; p++) {
      put_char(*p);
    }
    return *this;
  }
} fast_output;

// here puts define
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#define rint register int
#define rll register ll 
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fors(i, a, b) for (int i = (a); i <= (b); ++i)
#define _fors(i, a, b) for (int i = (a); i >= (b); --i)
#define cyc(m) fors(rqtwqtqwt, 1, m)
#define mp(a, b) make_pair(a, b)
#define mt(a, b, c) make_tuple(a, b, c)
#define mem(A, b) memset(A, b, sizeof(A))
#define all(X) (X).begin(), (X).end()
#define y0 gawgfawgawg
#define y1 sdfyseyegeh
#define pb push_back
#define eb emplace_back
#define cout fast_output
#define endl '\n'
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

int start_time;

const int _ = 1e5 + 5;

int n, m;
int k[_];
int l[_][2], r[_][2];
int las[_][2];
set<vector<int> > s[2];

void write(int cur, int kin) {
  if (cur == 0) return ;
  write(las[cur][kin], kin ^ 1);
  fors(i, las[cur][kin] + 1, cur) cout << kin << " \n"[i == n];
  return ;
}

bool in(int x, int id, int i) {
  return x >= l[id][i] && x <= r[id][i];
}

void solve() {
  cin >> n >> m;
  fors(i, 1, n) {
    cin >> k[i];
    cin >> l[i][0] >> r[i][0];
    cin >> l[i][1] >> r[i][1];
  }
  if (in(0, 1, 0) && in(k[1], 1, 1)) s[0].insert({0, 0});
  if (in(0, 1, 1) && in(k[1], 1, 0)) s[1].insert({0, 0});
  fors(i, 2, n) {
    int emp0 = s[0].empty(), emp1 = s[1].empty();
    if (!emp0) s[1].insert({k[i - 1], i - 1});
    if (!emp1) s[0].insert({k[i - 1], i - 1});
    if (in(k[i], i, 0)) {
      while (!s[1].empty() && !in((*s[1].begin())[0], i, 1)) s[1].erase(s[1].begin());
      while (!s[1].empty() && !in((*s[1].rbegin())[0], i, 1)) s[1].erase(s[1].lower_bound(*s[1].rbegin()));
    }
    else s[1].clear();
    if (in(k[i], i, 1)) {
      while (!s[0].empty() && !in((*s[0].begin())[0], i, 0)) s[0].erase(s[0].begin());
      while (!s[0].empty() && !in((*s[0].rbegin())[0], i, 0)) s[0].erase(s[0].lower_bound(*s[0].rbegin()));  
    }
    else s[0].clear();
    if (!s[0].empty()) las[i][1] = (*s[0].begin())[1];
    if (!s[1].empty()) las[i][0] = (*s[1].begin())[1]; 
  }
  if (s[0].empty() && s[1].empty()) { no; return ; }
  yes;
  if (!s[0].empty()) write(n, 1);
  else write(n, 0);
  return ;
}

signed main() {
  #ifdef Sakuyalove 
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif 
  ios::sync_with_stdio(false);
  cin.tie(0);
  start_time = clock();
  int T = 1;
  // cin >> T;
  while (T--) {
    solve();
  }

  #ifdef Sakuyalove
    cout << "time = " << clock() - start_time << endl;
  #endif

  return 0;
}
```