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;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n,h;
  cin>>n>>h;
  vector<Int> a(n),b(n),c(n),d(n);
  for(Int i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i]>>d[i];

  const Int MAX = 300;
  vector<vector<Int> > G(MAX*2);
  vector<Int> od(MAX*2,0),id(MAX*2,0);
  for(Int i=0;i<n;i++){
    Int l=c[i]==0? a[i]:-c[i];
    Int r=d[i]==0?-b[i]: d[i];
    G[MAX+l].emplace_back(MAX+r);
    od[MAX+l]++;
    id[MAX+r]++;
  }
  
  auto NO=[](){cout<<"NO"<<endl;exit(0);};
  
  Int w=0;
  for(Int i=1;i<MAX;i++){    
    while(od[MAX+i]>id[MAX+i]){
      G[MAX+w].emplace_back(MAX+i);
      od[MAX+w]++;
      id[MAX+i]++;
    }
    while(od[MAX-i]<id[MAX-i]){
      G[MAX-i].emplace_back(MAX-w);
      od[MAX-i]++;
      id[MAX-w]++;
    }
    //cout<<i<<"+:"<<od[MAX+i]<<" "<<id[MAX+i]<<endl;
    //cout<<i<<"-:"<<od[MAX-i]<<" "<<id[MAX-i]<<endl;
    if(od[MAX+i]!=id[MAX+i]) NO();
    if(od[MAX-i]!=id[MAX-i]) NO();
  }

  vector<Int> used(MAX*2);
  queue<Int> q;

  used[MAX+w]=1;
  q.emplace(MAX+w);
  
  while(!q.empty()){
    Int v=q.front();q.pop();
    for(Int u:G[v]){
      if(used[u]) continue;
      used[u]=1;
      q.emplace(u);
    }
  }
  
  for(Int i=0;i<MAX*2;i++)
    if((id[i]||od[i])&&!used[i]) NO();
  
  cout<<"YES"<<endl;
  return 0;
}
