Problem statement

There are real variables $ X_1, X_2, ... $, and some initial value is assigned. From now on, $ Q $ pieces of information will be given in order. The information given is one of the following two types.

* min $ \\ {X_ {a_i}, X_ {a_i + 1}, ..., X_ {b_i} \\} = y_i $.
* Substitute $ y_i $ for the variables $ X_ {a_i}, X_ {a_i + 1}, ..., X_ {b_i} $.



Determine if you can choose the initial value of each variable so that these $ Q $ pieces of information are consistent.

Constraint

* $ 1 \ leq Q \ leq 5 \ times 10 ^ 4 $
* $ 0 \ leq t_i \ leq 1 $
* $ 1 \ leq a_i \ leq b_i \ leq 10 ^ 9 $
* $ 1 \ leq y_i \ leq 10 ^ 9 $



input

Input follows the following format. All given numbers are integers.


$ Q $
$ t_1 $ $ a_1 $ $ b_1 $ $ y_1 $
$ t_2 $ $ a_2 $ $ b_2 $ $ y_2 $
$ ... $
$ t_Q $ $ a_Q $ $ b_Q $ $ y_Q $

1. When $ t_i = 0 $, it indicates that min $ \\ {X_ {a_i}, X_ {a_i + 1}, ..., X_ {b_i} \\} = y_i $.
2. When $ t_i = 1 $, it indicates that $ y_i $ is assigned to $ X_ {a_i}, X_ {a_i + 1}, ..., X_ {b_i} $.

output

Output "YES" if there is an initial value that does not contradict all the information, otherwise output "NO" on one line.

Examples

Input

5
0 1 2 8
0 2 3 9
0 2 2 11
1 2 2 7
0 1 3 7


Output

YES


Input

2
1 10 100 333
0 100 1000 555


Output

NO
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

struct Node {
  int lower;
  int upper;
  Node() {;}
  Node(int lower, int upper)
    : lower(lower), upper(upper) {;}
};

inline Node Merge(Node left, Node right) {
  return Node(min(left.lower, right.lower), max(left.upper, right.upper));
}

struct SegmentTree {
  static const int MAX_DEPTH = 18;
  static const int SIZE = 1 << (MAX_DEPTH + 1);  // 2^18 = 262144

  bool updated[SIZE];
  Node data[SIZE];
  SegmentTree() { memset(updated, false, sizeof(updated)); }
  void change(int index, Node value) {
    int target = (1 << MAX_DEPTH) + index;
    data[target] = value;
    for (int i = 1; i <= MAX_DEPTH; i++) {
      target >>= 1;
      data[target] = Merge(data[target * 2], data[target * 2 + 1]);
    }
  }
  void set(Node v, int left, int right) {
    assert(left <= right);
    return in_set(v, 0, 1, left, right);
  }
  Node get(int left, int right) {
    assert(left <= right);
    return in_get(0, 1, left, right);
  }
private:
  void Divide(int node) {
    if (!updated[node] || node >= (1 << MAX_DEPTH)) { return; }
    updated[node] = false;
    updated[node * 2] = true;
    updated[node * 2 + 1] = true;
    data[node * 2] = data[node];
    data[node * 2 + 1] = data[node];
  }
  void in_set(Node v, int depth, int node, int left, int right) {
    int width = 1 << (MAX_DEPTH - depth);
    int index = node - (1 << depth);
    int node_left = index * width;
    int node_mid = node_left + (width >> 1);

    Divide(node);
    if (right - left + 1 == width && left == node_left) {
      updated[node] = true;
      data[node] = v;
    } else {
      if (right < node_mid) {
        in_set(v, depth + 1, node * 2, left, right);
      } else if (left >= node_mid) {
        in_set(v, depth + 1, node * 2 + 1, left, right);
      } else {
        in_set(v, depth + 1, node * 2, left, node_mid - 1);
        in_set(v, depth + 1, node * 2 + 1, node_mid, right);
      }
      data[node] = Merge(data[node * 2], data[node * 2 + 1]);
    }
  }
  Node in_get(int depth, int node, int left, int right) {
    int width = 1 << (MAX_DEPTH - depth);
    int index = node - (1 << depth);
    int node_left = index * width;
    int node_mid = node_left + (width >> 1);

    Divide(node);
    if (right - left + 1 == width && left == node_left) {
      return data[node];
    } else if (right < node_mid) {
      return in_get(depth + 1, node * 2, left, right);
    } else if (left >= node_mid) {
      return in_get(depth + 1, node * 2 + 1, left, right);
    }
    return Merge(in_get(depth + 1, node * 2, left, node_mid - 1), in_get(depth + 1, node * 2 + 1, node_mid, right));
  }
};

enum {
  QUERY_IN,
  QUERY_OUT,
  ASSIGN_IN,
  ASSIGN_OUT
};
struct Event {
  int index;
  int type;
  int x;
  int v;
  Event() {;}
  Event(int index, int type, int x, int v) :
    index(index), type(type), x(x), v(v) {;}
  bool operator<(const Event &rhs) const {
    return x < rhs.x;
  }
};

int t[50010];
int a[50010];
int b[50010];
int y[50010];
int q;
int n, m;
int ini[200010];
SegmentTree stree;
vector<Event> events;

void CalcIni() {
  MEMSET(stree.data, -1);
  int pos = 0;
  set<int> constraints;
  constraints.insert(q);
  set<int> rest;
  REP(i, n) {
    while (pos < (int)events.size() && events[pos].x == i) {
      Event e = events[pos++];
      if (e.type == QUERY_IN) {
        stree.change(e.index, Node(e.v, e.v));
        rest.insert(e.index);
      } else if (e.type == QUERY_OUT) {
        stree.change(e.index, Node(-1, -1));
        rest.erase(e.index);
      } else if (e.type == ASSIGN_IN) {
        constraints.insert(e.index);
      } else if (e.type == ASSIGN_OUT) {
        constraints.erase(e.index);
      }
    }
    ini[i] = stree.get(0, *constraints.begin()).upper;
  }
}

bool Check() {
  stree = SegmentTree();
  MEMSET(stree.data, 1 << 30);
  REP(i, n) { stree.change(i, Node(ini[i], ini[i])); }
  REP(i, q) {
    if (t[i] == 0) {
      if (stree.get(a[i], b[i]).lower != y[i]) { return false; }
    } else {
      stree.set(Node(y[i], y[i]), a[i], b[i]);
    }
  }
  return true;
}

int main() {
  while (scanf("%d", &q) > 0) {
    events.clear();
    n = m = 0;
    {
      set<int> open1;
      set<int> open2;
      REP(i, q) {
        scanf("%d %d %d %d", &t[i], &a[i], &b[i], &y[i]);
        open1.insert(a[i]);
        open1.insert(b[i]);
        open1.insert(b[i] + 1);
        open2.insert(y[i]);
      }
      map<int, int> mapto1;
      map<int, int> mapto2;
      FORIT(it, open1) {
        mapto1[*it] = n++;
      }
      FORIT(it, open2) {
        mapto2[*it] = m++;
      }
      REP(i, q) {
        a[i] = mapto1[a[i]];
        b[i] = mapto1[b[i]];
        y[i] = mapto2[y[i]];
      }
    }
    REP(i, q) {
      events.push_back(Event(i, 2 * t[i], a[i], y[i]));
      events.push_back(Event(i, 2 * t[i] + 1, b[i] + 1, y[i]));
    }
    sort(events.begin(), events.end());
    CalcIni();
    puts(Check() ? "YES" : "NO");
  }
}