We have N irregular jigsaw pieces. Each piece is composed of three rectangular parts of width 1 and various heights joined together. More specifically:

* The i-th piece is a part of height H, with another part of height A_i joined to the left, and yet another part of height B_i joined to the right, as shown below. Here, the bottom sides of the left and right parts are respectively at C_i and D_i units length above the bottom side of the center part.



<image>

Snuke is arranging these pieces on a square table of side 10^{100}. Here, the following conditions must be held:

* All pieces must be put on the table.
* The entire bottom side of the center part of each piece must touch the front side of the table.
* The entire bottom side of the non-center parts of each piece must either touch the front side of the table, or touch the top side of a part of some other piece.
* The pieces must not be rotated or flipped.



Determine whether such an arrangement is possible.

Constraints

* 1 \leq N \leq 100000
* 1 \leq H \leq 200
* 1 \leq A_i \leq H
* 1 \leq B_i \leq H
* 0 \leq C_i \leq H - A_i
* 0 \leq D_i \leq H - B_i
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N H
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
:
A_N B_N C_N D_N


Output

If it is possible to arrange the pieces under the conditions, print `YES`; if it is impossible, print `NO`.

Examples

Input

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


Output

YES


Input

4 2
1 1 0 1
1 1 0 1
1 1 0 1
1 1 0 1


Output

NO


Input

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


Output

YES
#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL) INF;

const int MAX = 1010;

VI g[MAX];
int IN[MAX];
int OUT[MAX];
bool U[MAX];

int L, R;

void no()
{
	cout<<"NO"<<endl;
	exit(0);
}

void dfs(int x)
{
	U[x] = true;

	if (x & 1)
	{
		if (IN[x] > OUT[x]) no();
		R += IN[x] - OUT[x];
	}
	else
	{
		if (OUT[x] > IN[x]) no();
		L += OUT[x] - IN[x];
	}

	FOR (i, 0, SZ(g[x]))
	{
		int to = g[x][i];
		if (U[to]) continue;
		dfs(to);
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);

	int n, m;
	scanf("%d%d", &n, &m);
	FOR (i, 0, n)
	{
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);

		int x, y;
		if (d == 0) y = b * 2;
		else y = d * 2 + 1;

		if (c == 0) x = a * 2 + 1;
		else x = c * 2;

	//	cout<<x<<' '<<y<<endl;
	//	cout<<a<<' '<<b<<' '<<c<<' '<<d<<endl;

		g[x].PB(y);
		g[y].PB(x);
		OUT[x]++;
		IN[y]++;
	}

	int c1 = 0, c2 = 0;
	FOR (i, 0, MAX)
	{
		if (U[i]) continue;
		if (SZ(g[i]) == 0) continue;
		L = R = 0;

		dfs(i);

		c1++;
		if (L == 0) c2++;
	}
	//cout<<"*"<<endl;
	if (c2) no();
	cout<<"YES"<<endl;

}

