Problem: Queries with Six Inequeties

Given a set of four integer pairs (a, b, c, d).

The jth query determines if i exists, x_j <a_i <y_j <b_i and z_j <c_i <w_j <d_i.

input


N Q
a_1 b_1 c_1 d_1
a_2 b_2 c_2 d_2
::
a_n b_n c_n d_n
x_1 y_1 z_1 w_1
x_2 y_2 z_2 w_2
::
x_q y_q z_q w_q


output


ans_1
ans_2
::
ans_q


On line j, print the answer to the jth query.

If the subscript i that satisfies the condition exists, `Yes` is output, and if it does not exist,` No` is output.

Constraint

* 1 \ leq N, Q \ leq 10 ^ 5
* 1 \ leq a_i <b_i \ leq 10 ^ 5
* 1 \ leq c_i <d_i \ leq 10 ^ 5
* 1 \ leq x_j <y_j \ leq 10 ^ 5
* 1 \ leq z_j <w_j \ leq 10 ^ 5



Input example


twenty two
14 86 9 121
3 34 3 34
1 14 5 14
1 9 1 9


Output example


No
Yes






Example

Input

2 2
14 86 9 121
3 34 3 34
1 14 5 14
1 9 1 9


Output

No
Yes

Solution (in CPP):

Solution:
#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;}


struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;

//INSERT ABOVE HERE
signed main(){
  int n,q;
  cin>>n>>q;
  struct Point{
    int a,b,c,d;
    Point(int a,int b,int c,int d):
      a(a),b(b),c(c),d(d){}
  };

  auto cmpX=[&](Point p,Point q){return p.a<q.a;};
  auto cmpY=[&](Point p,Point q){return p.c<q.c;};

  const int BS1 = 512;
  const int BS2 = 32;
  assert(BS1 % BS2 == 0);

  vector<Point> ps;
  for(int i=0;i<n;i++){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    ps.emplace_back(a,b,c,d);
  }

  while(ps.size()%BS1)
    ps.emplace_back(0,0,0,0);

  n=ps.size();
  sort(ps.begin(),ps.end(),cmpX);

  using P = pair<int, int>;
  vector< vector<P> > qs(n/BS2);

  vector<int> ma(n,1e6),Ma(n,0);
  vector<int> mc(n,1e6),Mc(n,0);
  for(int i=0;i<n;i+=BS1){

    for(int j=0;j<BS1;j++){
      chmin(ma[i],ps[i+j].a);
      chmax(Ma[i],ps[i+j].a);
    }

    sort(ps.begin()+i,ps.begin()+i+BS1,cmpY);
    for(int j=0;j<BS1;j+=BS2){
      auto &vp=qs[(i+j)/BS2];
      for(int k=0;k<BS2;k++){
        int z=i+j+k;
        vp.emplace_back(ps[z].b,ps[z].d);
        chmin(mc[i],ps[z].c);
        chmax(Mc[i],ps[z].c);
      }

      vp.emplace_back(-1,1e6);
      vp.emplace_back(1e6,-1);
      sort(vp.begin(),vp.end());
      vector<P> vq;
      for(auto p:vp)
        if(vq.empty()||vq.back().second>p.second)
          vq.emplace_back(p);
      vp=vq;
    }
  }


  for(int t=0;t<q;t++){
    int x,y,z,w;
    cin>>x>>y>>z>>w;

    auto check=
      [&](int k){
        return x<ps[k].a && ps[k].a<y && y<ps[k].b && z<ps[k].c && ps[k].c<w && w<ps[k].d;
      };

    int flg=0;
    for(int i=0;i<n;i+=BS1){
      if(flg) break;
      if(Ma[i]<=x) continue;
      if(y<=ma[i]) continue;

      if(x<ma[i]&&Ma[i]<y){
        for(int j=0;j<BS1;j+=BS2){
          if(Mc[i]<=z) continue;
          if(w<=mc[i]) continue;
          if(z<mc[i]&&Mc[i]<w){
            auto &vp=qs[(i+j)/BS2];
            flg|=w<lower_bound(vp.begin(),vp.end(),P(y,1e6))->second;
            continue;
          }
          for(int k=0;k<BS2;k++) flg|=check(i+j+k);
        }
        continue;
      }
      for(int j=0;j<BS1;j++) flg|=check(i+j);
    }

    const int DEBUG = 0;
    if(DEBUG){
      int flg2=0;
      for(int i=0;i<n;i++) flg2|=check(i);
      if(flg!=flg2) cerr<<flg<<" "<<flg2<<endl;
      assert(flg == flg2);
    }
    cout<<(flg?"Yes":"No")<<"\n";
  }
  cout<<flush;
  return 0;
}