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;
template <class T = int> using V = vector<T>;
template <class T = int> using VV = V< V<T> >;

struct Sparse2DSegmentTree {
  using T = int;
  static T op(const T& a, const T& b) { return max(a, b); }
  static constexpr T e() { return -1; }

  struct SegmentTree {
    const int n;
    V<T> t;
    SegmentTree(int _n) : n(_n), t(2 * n, e()) {}
    T& operator[](int i) { return t[i + n]; }
    T acc(int l, int r) const {
      T res = e();
      for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res = op(res, t[l++]);
        if (r & 1) res = op(res, t[--r]);
      }
      return res;
    }
    void set(int i, const T& a) {
      t[i += n] = a;
      while (i >>= 1) t[i] = op(t[2 * i], t[2 * i + 1]);
    }
  };
  const int n;
  V<SegmentTree> st;
  VV<> ys;
  Sparse2DSegmentTree(int _n) : n(_n), ys(2 * n) {}
  void preset(int x, int y) {
    for (x += n; x; x >>= 1) ys[x].push_back(y);
  }
  void build() {
    for (auto&& v : ys) {
      sort(begin(v), end(v));
      v.erase(unique(begin(v), end(v)), end(v));
      st.emplace_back(v.size());
    }
  }
  int zip(int x, int y) const { return lower_bound(begin(ys[x]), end(ys[x]), y) - begin(ys[x]); }
  T acc(int x0, int x1, int y0, int y1) const {
    T res = e();
    for (x0 += n, x1 += n; x0 < x1; x0 >>= 1, x1 >>= 1) {
      if (x0 & 1) res = op(res, st[x0].acc(zip(x0, y0), zip(x0, y1))), ++x0;
      if (x1 & 1) --x1, res = op(res, st[x1].acc(zip(x1, y0), zip(x1, y1)));
    }
    return res;
  }
  void set(int x, int y, const T& a) {
    x += n, st[x].set(zip(x, y), a);
    while (x >>= 1) {
      T l = st[2 * x].acc(zip(2 * x, y), zip(2 * x, y + 1));
      T r = st[2 * x + 1].acc(zip(2 * x + 1, y), zip(2 * x + 1, y + 1));
      st[x].set(zip(x, y), op(l, r));
    }
  }
};

constexpr int lim = 1e5;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  struct Rec {
    int a, b, c, d;
  };
  vector< vector<Rec> > rec(lim);
  Sparse2DSegmentTree st(lim);
  for (int i = 0; i < n; ++i) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    --a, --b, --c, --d;
    rec[b].emplace_back(Rec{a, b, c, d});
    st.preset(a, c);
  }
  st.build();
  struct Query {
    int id, x, y, z, w;
  };
  vector< vector<Query> > qs(lim);
  for (int i = 0; i < q; ++i) {
    int x, y, z, w;
    cin >> x >> y >> z >> w;
    --x, --y, --z, --w;
    qs[y].emplace_back(Query{i, x, y, z, w});
  }
  vector<bool> res(q);
  for (int t = lim; t--; ) {
    for (auto e : qs[t]) {
      res[e.id] = st.acc(e.x + 1, e.y, e.z + 1, e.w) > e.w;
    }
    for (auto e : rec[t]) {
      st.set(e.a, e.c, e.d);
    }
  }
  for (auto e : res) {
    cout << (e ? "Yes" : "No") << '\n';
  }
}