#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <sstream>
#include <cstring>
#include <numeric>
#include <ctime>
#include <cassert>
#include <random>
#include <valarray>
//#include <fstream>

#define re return
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)(x).size())
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define y0 y32479
#define y1 y95874
#define next next239
#define prev prev239
#define fill(x, y) memset(x, y, sizeof(x))
#define sqr(x) ((x)*(x))
#define sqrt(x) sqrt(abs(x))
#define unq(x) (x.resize(unique(all(x)) - x.begin()))
#define ba back()
#define popcount __builtin_popcountll
#define fastIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}

#ifdef LOCAL_BOBER
bool local = true;
#define deb(x) cout << #x << " = " << (x) << endl
#define debn(x, n) { cout << #x << "(" << n << ") = " << \
	"{"; int _f_ = 1; rep(_i_, n) {if (!_f_) cout << "|"; cout << x[_i_]; _f_= 0;} cout << "}" << endl;}
#define deba(x) { cout << #x << " (size: " << sz(x) << ") = " << \
	"{"; int _f_ = 1; for (auto o : x) {if (!_f_) cout << "|"; cout << o; _f_ = 0;} cout << "}" << endl;}
#else
bool local = false;
#define deb(x) ;
#define debn(x, n) ;
#define deba(x) ;
#define endl "\n"
#endif

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef pair<double, double> pdd;
typedef long double LD;
typedef double D;

template<class T> void print(T v) { cout << sz(v) << endl; for (auto x : v) cout << x << ' '; cout << endl; };
template<class T> void print1(T v) { cout << sz(v) << endl; for (auto x : v) cout << x + 1 << ' '; cout << endl; };
template<class T1, class T2> ostream& operator << (ostream &o, pair<T1, T2> x) {re o << x.fi << ' ' << x.se;}
template<class T1, class T2> istream& operator >> (istream &o, pair<T1, T2> &x) {re o >> x.fi >> x.se;}
template<class T1, class T2> pair<T1, T2> operator + (pair<T1, T2> a, pair<T1, T2> b) {a.fi += b.fi; a.se += b.se; re a;}
template<class T1, class T2> pair<T1, T2> operator - (pair<T1, T2> a, pair<T1, T2> b) {a.fi -= b.fi; a.se -= b.se; re a;}
template<class T1, class T2> void operator += (pair<T1, T2> &a, pair<T1, T2> b) {a.fi += b.fi; a.se += b.se;}
template<class T1, class T2> void operator -= (pair<T1, T2> &a, pair<T1, T2> b) {a.fi -= b.fi; a.se -= b.se;}

int nint() {int x; cin >> x; re x;}
double getTime() { re clock() / (double) CLOCKS_PER_SEC;};

mt19937 rnd(0);
int rand(int n) { re rnd() % n; }
int rand(int l, int r) { re rnd() % (r - l + 1) + l; }

const int mod = 1000000000 + 7;

void initIO() {
	if (local) {
		freopen("input.txt", "r", stdin);
		//freopen("output.txt", "w", stdout);
		srand((int)time(0));
		rnd.seed((int)time(0));
	}
	else {
		//freopen("input.txt", "r", stdin);
		//freopen("output.txt", "w", stdout);
		fastIO();
	}
}

void solve();

signed main() {
	initIO();

	int tc = 1;
//	cin >> tc;
	rep(tt, tc) {
//		cout << "Case #" << tt + 1 << ": ";
		solve();
	}

//	if (local)
//		cout << endl << "time = " << getTime() << endl;
}


/* ================ actual code starts here ================ */

int n;
int m;

int k[100500], al[100500], ar[100500], bl[100500], br[100500];
int valL[2][100500], valR[2][100500];
int mi[2][20][100500], ma[2][20][100500];

void calc() {
	rep(id, 2) {
		rep(i, n) {
			mi[id][0][i] = valR[id][i];
			ma[id][0][i] = valL[id][i];
		}
		for (int t = 1; t < 20; t++)
		rep(i, n) {
			mi[id][t][i] = mi[id][t - 1][i];
			ma[id][t][i] = ma[id][t - 1][i];
			int tmp = i + (1 << (t - 1));
			if (tmp < n) {
				mi[id][t][i] = min(mi[id][t][i], mi[id][t - 1][tmp]);
				ma[id][t][i] = max(ma[id][t][i], ma[id][t - 1][tmp]);
			}
		}
	}
}

int checka(int x, int p) {
	re al[p] <= x && ar[p] >= x;
}

int checkb(int x, int p) {
	re bl[p] <= x && br[p] >= x;
}

struct dno {
	int val;
	dno* pre;

	dno() {
		val = 0;
		pre = 0;
	}

	dno(int x, dno* p) {
		pre = p;
		val = x;
	}
};

int getmin(int id, int l, int r) {
	int t = 19;
	while (l + (1 << t) - 1 > r)
		t--;
	int ans = mi[id][t][l];
	r -= (1 << t);
	r++;
	ans = min(ans, mi[id][t][r]);
	re ans;
}

int getmax(int id, int l, int r) {
	int t = 19;
	while (l + (1 << t) - 1 > r)
		t--;
	int ans = ma[id][t][l];
	r -= (1 << t);
	r++;
	ans = max(ans, ma[id][t][r]);
	re ans;
}

int get(int x, int p, int z) {
	int l = p, r = n - 1, ans = l;
	while (l <= r) {
		int c = (l + r) / 2;
		int val1 = getmax(z, p, c);
		int val2 = getmin(z, p, c);
		if (val1 <= x && x <= val2) {
			ans = c;
			l = c + 1;
		}
		else
			r = c - 1;
	}
	re ans;
}

int getl(int x, int p) {
	if (!checka(x, p))
		re -1;
	re get(x, p, 0);
}

int getr(int x, int p) {
	if (!checkb(x, p))
		re -1;
	re get(x, p, 1);
}

struct botva {
	int l, r;
	int dl, dr;
	dno* path;
	int bad;

	botva() {
		l = r = 0;
		path = 0;
		dl = dr = 0;
		bad = 0;
	}

	void update(int p) {
		if (bad) {
			dl = dr = -1;
			re;
		}

		dl = getl(l, p);
		dr = getr(r, p);
		if (dl < p || dr < p) {
			dl = dr = -1;
			bad = 1;
		}
	}
};

void solve() {
	cin >> n >> m;
	rep(i, n) {
		cin >> k[i] >> al[i] >> ar[i] >> bl[i] >> br[i];
		valL[0][i] = al[i];
		valL[1][i] = bl[i];
		valR[0][i] = ar[i];
		valR[1][i] = br[i];
	}

	calc();

	botva b1, b2;
	rep(i, n) {
		botva a1, a2;

		botva t1 = b1;
		botva t2 = b2;
		t1.l = k[i];
		t1.update(i);

		t2.l = k[i];
		t2.update(i);

		if (t1.dr > t2.dr)
			a1 = t1;
		else
			a1 = t2;

		t1 = b1;
		t2 = b2;
		t1.r = k[i];
		t1.update(i);
		t2.r = k[i];
		t2.update(i);

		if (t1.dl > t2.dl)
			a2 = t1;
		else
			a2 = t2;

		if (a1.bad && a2.bad) {
			cout << "No" << endl;
			re;
		}

		a1.path = new dno(0, a1.path);
		a2.path = new dno(1, a2.path);
		b1 = a1;
		b2 = a2;
	}

	cout << "Yes" << endl;
	vi v;
	dno* cur = b1.path;
	if (b1.bad)
		cur = b2.path;

	while (cur) {
		v.pb(cur->val);
		cur = cur->pre;
	}
	reverse(all(v));
	for (int x : v)
		cout << x << ' ';
}













### Prompt

Please provide a cpp coded solution to the problem described below:

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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <sstream>
#include <cstring>
#include <numeric>
#include <ctime>
#include <cassert>
#include <random>
#include <valarray>
//#include <fstream>

#define re return
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)(x).size())
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define y0 y32479
#define y1 y95874
#define next next239
#define prev prev239
#define fill(x, y) memset(x, y, sizeof(x))
#define sqr(x) ((x)*(x))
#define sqrt(x) sqrt(abs(x))
#define unq(x) (x.resize(unique(all(x)) - x.begin()))
#define ba back()
#define popcount __builtin_popcountll
#define fastIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}

#ifdef LOCAL_BOBER
bool local = true;
#define deb(x) cout << #x << " = " << (x) << endl
#define debn(x, n) { cout << #x << "(" << n << ") = " << \
	"{"; int _f_ = 1; rep(_i_, n) {if (!_f_) cout << "|"; cout << x[_i_]; _f_= 0;} cout << "}" << endl;}
#define deba(x) { cout << #x << " (size: " << sz(x) << ") = " << \
	"{"; int _f_ = 1; for (auto o : x) {if (!_f_) cout << "|"; cout << o; _f_ = 0;} cout << "}" << endl;}
#else
bool local = false;
#define deb(x) ;
#define debn(x, n) ;
#define deba(x) ;
#define endl "\n"
#endif

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef pair<double, double> pdd;
typedef long double LD;
typedef double D;

template<class T> void print(T v) { cout << sz(v) << endl; for (auto x : v) cout << x << ' '; cout << endl; };
template<class T> void print1(T v) { cout << sz(v) << endl; for (auto x : v) cout << x + 1 << ' '; cout << endl; };
template<class T1, class T2> ostream& operator << (ostream &o, pair<T1, T2> x) {re o << x.fi << ' ' << x.se;}
template<class T1, class T2> istream& operator >> (istream &o, pair<T1, T2> &x) {re o >> x.fi >> x.se;}
template<class T1, class T2> pair<T1, T2> operator + (pair<T1, T2> a, pair<T1, T2> b) {a.fi += b.fi; a.se += b.se; re a;}
template<class T1, class T2> pair<T1, T2> operator - (pair<T1, T2> a, pair<T1, T2> b) {a.fi -= b.fi; a.se -= b.se; re a;}
template<class T1, class T2> void operator += (pair<T1, T2> &a, pair<T1, T2> b) {a.fi += b.fi; a.se += b.se;}
template<class T1, class T2> void operator -= (pair<T1, T2> &a, pair<T1, T2> b) {a.fi -= b.fi; a.se -= b.se;}

int nint() {int x; cin >> x; re x;}
double getTime() { re clock() / (double) CLOCKS_PER_SEC;};

mt19937 rnd(0);
int rand(int n) { re rnd() % n; }
int rand(int l, int r) { re rnd() % (r - l + 1) + l; }

const int mod = 1000000000 + 7;

void initIO() {
	if (local) {
		freopen("input.txt", "r", stdin);
		//freopen("output.txt", "w", stdout);
		srand((int)time(0));
		rnd.seed((int)time(0));
	}
	else {
		//freopen("input.txt", "r", stdin);
		//freopen("output.txt", "w", stdout);
		fastIO();
	}
}

void solve();

signed main() {
	initIO();

	int tc = 1;
//	cin >> tc;
	rep(tt, tc) {
//		cout << "Case #" << tt + 1 << ": ";
		solve();
	}

//	if (local)
//		cout << endl << "time = " << getTime() << endl;
}


/* ================ actual code starts here ================ */

int n;
int m;

int k[100500], al[100500], ar[100500], bl[100500], br[100500];
int valL[2][100500], valR[2][100500];
int mi[2][20][100500], ma[2][20][100500];

void calc() {
	rep(id, 2) {
		rep(i, n) {
			mi[id][0][i] = valR[id][i];
			ma[id][0][i] = valL[id][i];
		}
		for (int t = 1; t < 20; t++)
		rep(i, n) {
			mi[id][t][i] = mi[id][t - 1][i];
			ma[id][t][i] = ma[id][t - 1][i];
			int tmp = i + (1 << (t - 1));
			if (tmp < n) {
				mi[id][t][i] = min(mi[id][t][i], mi[id][t - 1][tmp]);
				ma[id][t][i] = max(ma[id][t][i], ma[id][t - 1][tmp]);
			}
		}
	}
}

int checka(int x, int p) {
	re al[p] <= x && ar[p] >= x;
}

int checkb(int x, int p) {
	re bl[p] <= x && br[p] >= x;
}

struct dno {
	int val;
	dno* pre;

	dno() {
		val = 0;
		pre = 0;
	}

	dno(int x, dno* p) {
		pre = p;
		val = x;
	}
};

int getmin(int id, int l, int r) {
	int t = 19;
	while (l + (1 << t) - 1 > r)
		t--;
	int ans = mi[id][t][l];
	r -= (1 << t);
	r++;
	ans = min(ans, mi[id][t][r]);
	re ans;
}

int getmax(int id, int l, int r) {
	int t = 19;
	while (l + (1 << t) - 1 > r)
		t--;
	int ans = ma[id][t][l];
	r -= (1 << t);
	r++;
	ans = max(ans, ma[id][t][r]);
	re ans;
}

int get(int x, int p, int z) {
	int l = p, r = n - 1, ans = l;
	while (l <= r) {
		int c = (l + r) / 2;
		int val1 = getmax(z, p, c);
		int val2 = getmin(z, p, c);
		if (val1 <= x && x <= val2) {
			ans = c;
			l = c + 1;
		}
		else
			r = c - 1;
	}
	re ans;
}

int getl(int x, int p) {
	if (!checka(x, p))
		re -1;
	re get(x, p, 0);
}

int getr(int x, int p) {
	if (!checkb(x, p))
		re -1;
	re get(x, p, 1);
}

struct botva {
	int l, r;
	int dl, dr;
	dno* path;
	int bad;

	botva() {
		l = r = 0;
		path = 0;
		dl = dr = 0;
		bad = 0;
	}

	void update(int p) {
		if (bad) {
			dl = dr = -1;
			re;
		}

		dl = getl(l, p);
		dr = getr(r, p);
		if (dl < p || dr < p) {
			dl = dr = -1;
			bad = 1;
		}
	}
};

void solve() {
	cin >> n >> m;
	rep(i, n) {
		cin >> k[i] >> al[i] >> ar[i] >> bl[i] >> br[i];
		valL[0][i] = al[i];
		valL[1][i] = bl[i];
		valR[0][i] = ar[i];
		valR[1][i] = br[i];
	}

	calc();

	botva b1, b2;
	rep(i, n) {
		botva a1, a2;

		botva t1 = b1;
		botva t2 = b2;
		t1.l = k[i];
		t1.update(i);

		t2.l = k[i];
		t2.update(i);

		if (t1.dr > t2.dr)
			a1 = t1;
		else
			a1 = t2;

		t1 = b1;
		t2 = b2;
		t1.r = k[i];
		t1.update(i);
		t2.r = k[i];
		t2.update(i);

		if (t1.dl > t2.dl)
			a2 = t1;
		else
			a2 = t2;

		if (a1.bad && a2.bad) {
			cout << "No" << endl;
			re;
		}

		a1.path = new dno(0, a1.path);
		a2.path = new dno(1, a2.path);
		b1 = a1;
		b2 = a2;
	}

	cout << "Yes" << endl;
	vi v;
	dno* cur = b1.path;
	if (b1.bad)
		cur = b2.path;

	while (cur) {
		v.pb(cur->val);
		cur = cur->pre;
	}
	reverse(all(v));
	for (int x : v)
		cout << x << ' ';
}













```