#include <bits/stdc++.h>
using namespace std;
const double long EPS = 1e-10;
struct wor {
  double long x = 0, y = 0;
};
double long dist(wor a, wor b) {
  double long answer =
      sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  return answer;
}
istream &operator>>(istream &is, vector<long long> &arr) {
  for (auto &e : arr) {
    is >> e;
  }
  return is;
}
pair<vector<double long>, vector<long long>> djkstra(
    long long from, long long n,
    vector<vector<pair<double long, long long>>> &adj) {
  vector<bool> used(n);
  vector<double long> d(n, 1e15);
  vector<long long> f(n);
  d[from] = 0;
  f[from] = from;
  for (int i = 0; i < n; i++) {
    long long mi = -1;
    for (int i = 0; i < n; i++) {
      if (!used[i]) {
        mi = i;
        break;
      }
    }
    for (int j = 0; j < n; j++) {
      if (!used[j] && d[j] < d[mi]) {
        mi = j;
      }
    }
    used[mi] = true;
    for (auto e : adj[mi]) {
      if (!used[e.second] && d[mi] + e.first < d[e.second]) {
        d[e.second] = d[mi] + e.first;
        f[e.second] = mi;
      }
    }
  }
  return {d, f};
}
struct Kun {
  long long n;
  vector<vector<long long>> adj;
  vector<long long> used;
  vector<bool> is_l;
  vector<long long> mt;
  Kun(long long n) {
    this->n = n;
    adj.resize(n);
    used.resize(n);
    mt.resize(n);
    is_l.resize(n);
  }
  void add_edge(long long u, long long v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  void make_left(long long v) { is_l[v] = true; }
  bool try_kun(long long v, long long cur) {
    if (used[v] == cur) return false;
    used[v] = cur;
    for (auto e : adj[v]) {
      if (mt[e] == -1 || try_kun(mt[e], cur)) {
        mt[e] = v;
        return true;
      }
    }
    return false;
  }
  long long max_matching() {
    vector<bool> usel(n);
    for (int i = 0; i < n; i++) {
      if (!is_l[i]) mt[i] = -1;
    }
    long long answer = 0;
    for (int i = 0; i < n; i++) {
      if (is_l[i]) {
        for (auto e : adj[i]) {
          if (mt[e] == -1) {
            mt[e] = i;
            answer++;
            usel[i] = true;
            break;
          }
        }
      }
    }
    long long z = 1;
    for (int i = 0; i < n; i++) {
      if (is_l[i] && !usel[i] && try_kun(i, z++)) answer++;
    }
    return answer;
  }
};
struct MCMF {
  struct edge {
    long long from, to, cap, flow, cost;
  };
  vector<edge> edges;
  vector<vector<long long>> adj;
  vector<long long> p;
  vector<long long> d;
  vector<long long> state;
  const long long lenin_inf = 2e9;
  long long n, s, t;
  MCMF(long long _n, long long _s, long long _t) {
    n = _n;
    s = _s;
    t = _t;
    p.resize(n);
    d.resize(n);
    state.resize(n);
    adj.resize(n);
  }
  void add_edge(long long from, long long to, long long cap, long long cost) {
    edge e1 = {from, to, cap, 0, cost};
    edge e2 = {to, from, 0, 0, -cost};
    adj[from].push_back(edges.size());
    edges.push_back(e1);
    adj[to].push_back(edges.size());
    edges.push_back(e2);
  }
  deque<long long> q;
  void relax(long long v, long long dist, long long from) {
    if (d[v] <= dist) return;
    d[v] = dist;
    p[v] = from;
    if (state[v] == 0 || (!q.empty() && d[v] < d[q.front()])) {
      q.push_front(v);
      state[v] = 1;
    } else if (state[v] == 2) {
      q.push_back(v);
      state[v] = 1;
    }
  }
  bool lenin() {
    fill(p.begin(), p.end(), -1);
    fill(d.begin(), d.end(), lenin_inf);
    fill(state.begin(), state.end(), 0);
    relax(s, 0, 0);
    while (!q.empty()) {
      long long v = q.front();
      q.pop_front();
      state[v] = 2;
      for (auto e : adj[v]) {
        if (edges[e].cap - edges[e].flow == 0) continue;
        relax(edges[e].to, d[v] + edges[e].cost, e);
      }
    }
    return d[t] < lenin_inf;
  }
  pair<long long, long long> max_flow() {
    long long cost = 0;
    long long flow = 0;
    while (lenin()) {
      long long ed = p[t];
      long long ma = edges[ed].cap - edges[ed].flow;
      while (edges[ed].from != s) {
        ma = min(ma, edges[ed].cap - edges[ed].flow);
        ed = p[edges[ed].from];
      }
      ma = min(ma, edges[ed].cap - edges[ed].flow);
      flow += ma;
      ed = p[t];
      while (edges[ed].from != s) {
        edges[ed].flow += ma;
        edges[ed ^ 1].flow -= ma;
        cost += ma * edges[ed].cost;
        ed = p[edges[ed].from];
      }
      edges[ed].flow += ma;
      edges[ed ^ 1].flow -= ma;
      cost += ma * edges[ed].cost;
    }
    return {cost, flow};
  }
};
struct Dinic {
  struct edge {
    long long from, to, cap, flow;
  };
  vector<edge> edges;
  vector<long long> ptr;
  vector<vector<long long>> adj;
  vector<long long> level;
  long long n, s, t;
  Dinic(long long _n, long long _s, long long _t) {
    n = _n;
    s = _s;
    t = _t;
    ptr.resize(n);
    adj.resize(n);
    level.resize(n);
  }
  void add_edge(long long from, long long to, long long cap, long long flow) {
    edge e1 = {from, to, cap, flow};
    edge e2 = {to, from, 0, -flow};
    adj[from].push_back(edges.size());
    edges.push_back(e1);
    adj[to].push_back(edges.size());
    edges.push_back(e2);
  }
  bool bfs() {
    queue<long long> q;
    fill(level.begin(), level.end(), -1);
    level[s] = 0;
    q.push(s);
    while (!q.empty()) {
      long long v = q.front();
      q.pop();
      for (auto e : adj[v]) {
        if (edges[e].cap - edges[e].flow == 0) continue;
        if (level[edges[e].to] == -1) {
          level[edges[e].to] = level[v] + 1;
          q.push(edges[e].to);
        }
      }
    }
    return level[t] != -1;
  }
  long long dfs(long long node, long long flow = 1e17) {
    if (node == t) {
      return flow;
    }
    for (long long &cid = ptr[node]; cid < adj[node].size(); cid++) {
      long long id = adj[node][cid];
      long long to = edges[id].to;
      if (level[node] + 1 != level[to] || edges[id].cap - edges[id].flow == 0)
        continue;
      long long added = dfs(to, min(flow, edges[id].cap - edges[id].flow));
      if (added) {
        edges[id].flow += added;
        edges[id ^ 1].flow -= added;
        return added;
      }
    }
    return 0;
  }
  long long flow() {
    long long answer = 0;
    while (bfs()) {
      fill(ptr.begin(), ptr.end(), 0);
      while (long long added = dfs(s)) {
        answer += added;
      }
    }
    return answer;
  }
};
void dfs(long long node, vector<vector<long long>> &adj, vector<bool> &used) {
  used[node] = true;
  for (auto e : adj[node]) {
    if (!used[e]) {
      dfs(e, adj, used);
    }
  }
}
bool vosh(vector<long long> &arr) {
  long long mi = arr[0];
  for (int i = 1; i < arr.size(); i++) {
    if (arr[i] <= mi) {
      mi = arr[i];
    } else {
      return true;
    }
  }
  return false;
}
struct ev {
  long long x, y1, y2, type, id;
};
bool comp(ev a, ev b) {
  if (a.x == b.x) return a.type < b.type;
  return a.x < b.x;
}
void preob(vector<pair<long long, long long>> &a) {
  set<long long> s;
  for (auto e : a) {
    s.insert(e.second);
    s.insert(e.first);
  }
  vector<long long> arr(s.size());
  long long z = 0;
  for (auto e : s) {
    arr[z] = e;
    z++;
  }
  for (auto &e : a) {
    e.first = lower_bound((arr).begin(), (arr).end(), e.first) - arr.begin();
    e.second = lower_bound((arr).begin(), (arr).end(), e.second) - arr.begin();
  }
}
const long long INF = 5e5;
long long t[4 * INF];
long long d[4 * INF];
void push(long long v) {
  if (d[v] != 0) {
    t[v] += d[v];
    d[2 * v + 1] += d[v];
    d[2 * v + 2] += d[v];
    d[v] = 0;
  }
}
void add(long long v, long long vl, long long vr, long long l, long long r,
         long long val) {
  push(v);
  if (vr < l || vl > r) {
    return;
  }
  if (l <= vl && vr <= r) {
    d[v] += val;
    push(v);
    return;
  }
  long long m = vl + (vr - vl) / 2;
  add(2 * v + 1, vl, m, l, r, val);
  add(2 * v + 2, m + 1, vr, l, r, val);
  t[v] = max(t[2 * v + 1], t[2 * v + 2]);
}
long long ma(long long v, long long vl, long long vr, long long l,
             long long r) {
  push(v);
  if (vr < l || vl > r) {
    return -1e17;
  }
  if (l <= vl && vr <= r) {
    return t[v];
  }
  long long m = vl + (vr - vl) / 2;
  return max(ma(2 * v + 1, vl, m, l, r), ma(2 * v + 2, m + 1, vr, l, r));
}
bool func(vector<pair<long long, long long>> &a,
          vector<pair<long long, long long>> &b) {
  long long am = 0;
  vector<ev> events;
  for (int i = 0; i < a.size(); i++) {
    events.push_back({a[i].first, b[i].first, b[i].second, 1, i});
    events.push_back({a[i].second, b[i].first, b[i].second, 2, i});
  }
  sort((events).begin(), (events).end(), comp);
  for (int i = 0; i < events.size(); i++) {
    if (events[i].type == 1) {
      long long z = ma(0, 0, INF - 1, events[i].y1, events[i].y2);
      if (z != am) return false;
      add(0, 0, INF - 1, events[i].y1, events[i].y2, 1);
      am++;
    } else {
      am--;
      add(0, 0, INF - 1, events[i].y1, events[i].y2, -1);
    }
  }
  return true;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  vector<pair<long long, long long>> a(n);
  vector<pair<long long, long long>> b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i].first >> a[i].second >> b[i].first >> b[i].second;
  }
  preob(a);
  preob(b);
  auto f = func(a, b);
  auto z = func(b, a);
  if (f && z) {
    cout << "YES";
  } else {
    cout << "NO";
  }
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

Filled with optimism, Hyunuk will host a conference about how great this new year will be!

The conference will have n lectures. Hyunuk has two candidate venues a and b. For each of the n lectures, the speaker specified two time intervals [sa_i, ea_i] (sa_i ≤ ea_i) and [sb_i, eb_i] (sb_i ≤ eb_i). If the conference is situated in venue a, the lecture will be held from sa_i to ea_i, and if the conference is situated in venue b, the lecture will be held from sb_i to eb_i. Hyunuk will choose one of these venues and all lectures will be held at that venue.

Two lectures are said to overlap if they share any point in time in common. Formally, a lecture held in interval [x, y] overlaps with a lecture held in interval [u, v] if and only if max(x, u) ≤ min(y, v).

We say that a participant can attend a subset s of the lectures if the lectures in s do not pairwise overlap (i.e. no two lectures overlap). Note that the possibility of attending may depend on whether Hyunuk selected venue a or venue b to hold the conference.

A subset of lectures s is said to be venue-sensitive if, for one of the venues, the participant can attend s, but for the other venue, the participant cannot attend s.

A venue-sensitive set is problematic for a participant who is interested in attending the lectures in s because the participant cannot be sure whether the lecture times will overlap. Hyunuk will be happy if and only if there are no venue-sensitive sets. Determine whether Hyunuk will be happy.

Input

The first line contains an integer n (1 ≤ n ≤ 100 000), the number of lectures held in the conference.

Each of the next n lines contains four integers sa_i, ea_i, sb_i, eb_i (1 ≤ sa_i, ea_i, sb_i, eb_i ≤ 10^9, sa_i ≤ ea_i, sb_i ≤ eb_i).

Output

Print "YES" if Hyunuk will be happy. Print "NO" otherwise.

You can print each letter in any case (upper or lower).

Examples

Input


2
1 2 3 6
3 4 7 8


Output


YES


Input


3
1 3 2 4
4 5 6 7
3 4 5 5


Output


NO


Input


6
1 5 2 9
2 4 5 8
3 6 7 11
7 10 12 16
8 11 13 17
9 12 14 18


Output


YES

Note

In second example, lecture set \{1, 3\} is venue-sensitive. Because participant can't attend this lectures in venue a, but can attend in venue b.

In first and third example, venue-sensitive set does not exist.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const double long EPS = 1e-10;
struct wor {
  double long x = 0, y = 0;
};
double long dist(wor a, wor b) {
  double long answer =
      sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  return answer;
}
istream &operator>>(istream &is, vector<long long> &arr) {
  for (auto &e : arr) {
    is >> e;
  }
  return is;
}
pair<vector<double long>, vector<long long>> djkstra(
    long long from, long long n,
    vector<vector<pair<double long, long long>>> &adj) {
  vector<bool> used(n);
  vector<double long> d(n, 1e15);
  vector<long long> f(n);
  d[from] = 0;
  f[from] = from;
  for (int i = 0; i < n; i++) {
    long long mi = -1;
    for (int i = 0; i < n; i++) {
      if (!used[i]) {
        mi = i;
        break;
      }
    }
    for (int j = 0; j < n; j++) {
      if (!used[j] && d[j] < d[mi]) {
        mi = j;
      }
    }
    used[mi] = true;
    for (auto e : adj[mi]) {
      if (!used[e.second] && d[mi] + e.first < d[e.second]) {
        d[e.second] = d[mi] + e.first;
        f[e.second] = mi;
      }
    }
  }
  return {d, f};
}
struct Kun {
  long long n;
  vector<vector<long long>> adj;
  vector<long long> used;
  vector<bool> is_l;
  vector<long long> mt;
  Kun(long long n) {
    this->n = n;
    adj.resize(n);
    used.resize(n);
    mt.resize(n);
    is_l.resize(n);
  }
  void add_edge(long long u, long long v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  void make_left(long long v) { is_l[v] = true; }
  bool try_kun(long long v, long long cur) {
    if (used[v] == cur) return false;
    used[v] = cur;
    for (auto e : adj[v]) {
      if (mt[e] == -1 || try_kun(mt[e], cur)) {
        mt[e] = v;
        return true;
      }
    }
    return false;
  }
  long long max_matching() {
    vector<bool> usel(n);
    for (int i = 0; i < n; i++) {
      if (!is_l[i]) mt[i] = -1;
    }
    long long answer = 0;
    for (int i = 0; i < n; i++) {
      if (is_l[i]) {
        for (auto e : adj[i]) {
          if (mt[e] == -1) {
            mt[e] = i;
            answer++;
            usel[i] = true;
            break;
          }
        }
      }
    }
    long long z = 1;
    for (int i = 0; i < n; i++) {
      if (is_l[i] && !usel[i] && try_kun(i, z++)) answer++;
    }
    return answer;
  }
};
struct MCMF {
  struct edge {
    long long from, to, cap, flow, cost;
  };
  vector<edge> edges;
  vector<vector<long long>> adj;
  vector<long long> p;
  vector<long long> d;
  vector<long long> state;
  const long long lenin_inf = 2e9;
  long long n, s, t;
  MCMF(long long _n, long long _s, long long _t) {
    n = _n;
    s = _s;
    t = _t;
    p.resize(n);
    d.resize(n);
    state.resize(n);
    adj.resize(n);
  }
  void add_edge(long long from, long long to, long long cap, long long cost) {
    edge e1 = {from, to, cap, 0, cost};
    edge e2 = {to, from, 0, 0, -cost};
    adj[from].push_back(edges.size());
    edges.push_back(e1);
    adj[to].push_back(edges.size());
    edges.push_back(e2);
  }
  deque<long long> q;
  void relax(long long v, long long dist, long long from) {
    if (d[v] <= dist) return;
    d[v] = dist;
    p[v] = from;
    if (state[v] == 0 || (!q.empty() && d[v] < d[q.front()])) {
      q.push_front(v);
      state[v] = 1;
    } else if (state[v] == 2) {
      q.push_back(v);
      state[v] = 1;
    }
  }
  bool lenin() {
    fill(p.begin(), p.end(), -1);
    fill(d.begin(), d.end(), lenin_inf);
    fill(state.begin(), state.end(), 0);
    relax(s, 0, 0);
    while (!q.empty()) {
      long long v = q.front();
      q.pop_front();
      state[v] = 2;
      for (auto e : adj[v]) {
        if (edges[e].cap - edges[e].flow == 0) continue;
        relax(edges[e].to, d[v] + edges[e].cost, e);
      }
    }
    return d[t] < lenin_inf;
  }
  pair<long long, long long> max_flow() {
    long long cost = 0;
    long long flow = 0;
    while (lenin()) {
      long long ed = p[t];
      long long ma = edges[ed].cap - edges[ed].flow;
      while (edges[ed].from != s) {
        ma = min(ma, edges[ed].cap - edges[ed].flow);
        ed = p[edges[ed].from];
      }
      ma = min(ma, edges[ed].cap - edges[ed].flow);
      flow += ma;
      ed = p[t];
      while (edges[ed].from != s) {
        edges[ed].flow += ma;
        edges[ed ^ 1].flow -= ma;
        cost += ma * edges[ed].cost;
        ed = p[edges[ed].from];
      }
      edges[ed].flow += ma;
      edges[ed ^ 1].flow -= ma;
      cost += ma * edges[ed].cost;
    }
    return {cost, flow};
  }
};
struct Dinic {
  struct edge {
    long long from, to, cap, flow;
  };
  vector<edge> edges;
  vector<long long> ptr;
  vector<vector<long long>> adj;
  vector<long long> level;
  long long n, s, t;
  Dinic(long long _n, long long _s, long long _t) {
    n = _n;
    s = _s;
    t = _t;
    ptr.resize(n);
    adj.resize(n);
    level.resize(n);
  }
  void add_edge(long long from, long long to, long long cap, long long flow) {
    edge e1 = {from, to, cap, flow};
    edge e2 = {to, from, 0, -flow};
    adj[from].push_back(edges.size());
    edges.push_back(e1);
    adj[to].push_back(edges.size());
    edges.push_back(e2);
  }
  bool bfs() {
    queue<long long> q;
    fill(level.begin(), level.end(), -1);
    level[s] = 0;
    q.push(s);
    while (!q.empty()) {
      long long v = q.front();
      q.pop();
      for (auto e : adj[v]) {
        if (edges[e].cap - edges[e].flow == 0) continue;
        if (level[edges[e].to] == -1) {
          level[edges[e].to] = level[v] + 1;
          q.push(edges[e].to);
        }
      }
    }
    return level[t] != -1;
  }
  long long dfs(long long node, long long flow = 1e17) {
    if (node == t) {
      return flow;
    }
    for (long long &cid = ptr[node]; cid < adj[node].size(); cid++) {
      long long id = adj[node][cid];
      long long to = edges[id].to;
      if (level[node] + 1 != level[to] || edges[id].cap - edges[id].flow == 0)
        continue;
      long long added = dfs(to, min(flow, edges[id].cap - edges[id].flow));
      if (added) {
        edges[id].flow += added;
        edges[id ^ 1].flow -= added;
        return added;
      }
    }
    return 0;
  }
  long long flow() {
    long long answer = 0;
    while (bfs()) {
      fill(ptr.begin(), ptr.end(), 0);
      while (long long added = dfs(s)) {
        answer += added;
      }
    }
    return answer;
  }
};
void dfs(long long node, vector<vector<long long>> &adj, vector<bool> &used) {
  used[node] = true;
  for (auto e : adj[node]) {
    if (!used[e]) {
      dfs(e, adj, used);
    }
  }
}
bool vosh(vector<long long> &arr) {
  long long mi = arr[0];
  for (int i = 1; i < arr.size(); i++) {
    if (arr[i] <= mi) {
      mi = arr[i];
    } else {
      return true;
    }
  }
  return false;
}
struct ev {
  long long x, y1, y2, type, id;
};
bool comp(ev a, ev b) {
  if (a.x == b.x) return a.type < b.type;
  return a.x < b.x;
}
void preob(vector<pair<long long, long long>> &a) {
  set<long long> s;
  for (auto e : a) {
    s.insert(e.second);
    s.insert(e.first);
  }
  vector<long long> arr(s.size());
  long long z = 0;
  for (auto e : s) {
    arr[z] = e;
    z++;
  }
  for (auto &e : a) {
    e.first = lower_bound((arr).begin(), (arr).end(), e.first) - arr.begin();
    e.second = lower_bound((arr).begin(), (arr).end(), e.second) - arr.begin();
  }
}
const long long INF = 5e5;
long long t[4 * INF];
long long d[4 * INF];
void push(long long v) {
  if (d[v] != 0) {
    t[v] += d[v];
    d[2 * v + 1] += d[v];
    d[2 * v + 2] += d[v];
    d[v] = 0;
  }
}
void add(long long v, long long vl, long long vr, long long l, long long r,
         long long val) {
  push(v);
  if (vr < l || vl > r) {
    return;
  }
  if (l <= vl && vr <= r) {
    d[v] += val;
    push(v);
    return;
  }
  long long m = vl + (vr - vl) / 2;
  add(2 * v + 1, vl, m, l, r, val);
  add(2 * v + 2, m + 1, vr, l, r, val);
  t[v] = max(t[2 * v + 1], t[2 * v + 2]);
}
long long ma(long long v, long long vl, long long vr, long long l,
             long long r) {
  push(v);
  if (vr < l || vl > r) {
    return -1e17;
  }
  if (l <= vl && vr <= r) {
    return t[v];
  }
  long long m = vl + (vr - vl) / 2;
  return max(ma(2 * v + 1, vl, m, l, r), ma(2 * v + 2, m + 1, vr, l, r));
}
bool func(vector<pair<long long, long long>> &a,
          vector<pair<long long, long long>> &b) {
  long long am = 0;
  vector<ev> events;
  for (int i = 0; i < a.size(); i++) {
    events.push_back({a[i].first, b[i].first, b[i].second, 1, i});
    events.push_back({a[i].second, b[i].first, b[i].second, 2, i});
  }
  sort((events).begin(), (events).end(), comp);
  for (int i = 0; i < events.size(); i++) {
    if (events[i].type == 1) {
      long long z = ma(0, 0, INF - 1, events[i].y1, events[i].y2);
      if (z != am) return false;
      add(0, 0, INF - 1, events[i].y1, events[i].y2, 1);
      am++;
    } else {
      am--;
      add(0, 0, INF - 1, events[i].y1, events[i].y2, -1);
    }
  }
  return true;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  vector<pair<long long, long long>> a(n);
  vector<pair<long long, long long>> b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i].first >> a[i].second >> b[i].first >> b[i].second;
  }
  preob(a);
  preob(b);
  auto f = func(a, b);
  auto z = func(b, a);
  if (f && z) {
    cout << "YES";
  } else {
    cout << "NO";
  }
  return 0;
}

```