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<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_map>
#include<unordered_set>
#define lol(i,n) for(ll i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;

using namespace std;
int NOEL(){
  cout<<"NO"<<endl;
  return 0;
}
string g(char a,string b){
  string res="";
  res.push_back(a);
  res+=b;
  return res;
}

unordered_map<string,ll> nz;

unordered_map<string,vector<string> >v;
unordered_set<string> vis;
bool done;
void dfs(string x){
  if(vis.find(x)!=vis.end())return;
  vis.insert(x);
  if(nz[x]!=0)done=1;
  for(auto y:v[x]){
    dfs(y);
  }
}
int main(){
    ll n,h;
    cin>>n>>h;
    lol(i,n){
      string a,b,c,d;cin>>a>>b>>c>>d;
      string s,t;
      if(c=="0")s=g('x',a);
      else s=g('y',c);
      nz[s]++;
      if(d=="0")t=g('y',b);
      else t=g('x',d);
      nz[t]--;
      //cout<<s<<" "<<t<<endl;
      v[s].push_back(t);
      v[t].push_back(s);
    }
    for(auto dat:nz){
      string key=dat.first;
      ll cnt=dat.second;
      //cout<<key<<" "<<cnt<<endl;
      //if(cnt>=2||cnt<=-2)return NOEL();
      if(cnt>0&&key[0]!='x')return NOEL();
      if(cnt<0&&key[0]!='y')return NOEL();
      if(vis.find(key)==vis.end()){
	done=0; dfs(key);
	if(done==0)return NOEL();
      }
    }
    cout<<"YES"<<endl;
    return 0;
}
