#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
struct debug {
  ~debug() { cerr << endl; }
  template <class c>
  debug& operator<<(c x) {
    cerr << x;
    return *this;
  }
  template <class c, class d>
  debug& operator<<(pair<c, d> x) {
    *this << "(" << x.first << ", " << x.second << ")";
    return *this;
  }
  template <class c>
  debug& operator<<(vector<c> x) {
    *this << "[";
    int f = 0;
    for (auto it : x) {
      *this << (f ? ", " : "");
      *this << it;
      f = 1;
    }
    *this << "]";
    return *this;
  }
};
struct segment {
  int l, r, w;
  segment(int _l, int _r, int _w) : l(_l), r(_r), w(_w) {}
  bool operator<(const segment& other) const { return w < other.w; }
};
int M = 2e6;
vector<int> segTree(4 * M);
vector<int> lazy(4 * M);
void push(int idx) {
  segTree[2 * idx] += lazy[idx];
  segTree[2 * idx + 1] += lazy[idx];
  segTree[idx] = min(segTree[2 * idx], segTree[2 * idx + 1]);
  lazy[2 * idx] += lazy[idx];
  lazy[2 * idx + 1] += lazy[idx];
  lazy[idx] = 0;
}
void update(int ul, int ur, int val, int idx = 1, int l = 1, int r = M) {
  if (ul > ur) return;
  if (ul == l && ur == r) {
    if (l != r) {
      lazy[idx] += val;
      push(idx);
    } else {
      segTree[idx] += val;
    }
    return;
  }
  push(idx);
  int mid = (l + r) / 2;
  update(ul, min(ur, mid), val, 2 * idx, l, mid);
  update(max(ul, mid + 1), ur, val, 2 * idx + 1, mid + 1, r);
  segTree[idx] = min(segTree[2 * idx], segTree[2 * idx + 1]);
}
int getMin(int ql, int qr, int idx = 1, int l = 1, int r = M) {
  if (ql > qr) return 1e9;
  if (ql == l && qr == r) {
    if (l != r) {
      push(idx);
    }
    return segTree[idx];
  }
  push(idx);
  int mid = (l + r) / 2;
  return min(getMin(ql, min(mid, qr), 2 * idx, l, mid),
             getMin(max(ql, mid + 1), qr, 2 * idx + 1, mid + 1, r));
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  M = 2 * m;
  vector<segment> v;
  for (int i = 0; i < n; i++) {
    int l, r, w;
    scanf("%d%d%d", &l, &r, &w);
    v.push_back(segment(2 * l, 2 * r, w));
  }
  sort(v.begin(), v.end());
  int ans = 1e9;
  int lP = 0;
  update(v[0].l, v[0].r, 1);
  if (getMin(2, 2 * m) == 1) ans = 0;
  for (int i = 1; i < n; i++) {
    update(v[i].l, v[i].r, 1);
    while (lP <= i) {
      update(v[lP].l, v[lP].r, -1);
      if (getMin(2, 2 * m) == 0) {
        update(v[lP].l, v[lP].r, 1);
        break;
      }
      lP++;
    }
    if (getMin(2, 2 * m) >= 1) {
      ans = min(ans, v[i].w - v[lP].w);
    }
  }
  printf("%d\n", ans);
}

### Prompt

In Cpp, your task is to solve the following problem:

You are given n segments on a number line, numbered from 1 to n. The i-th segments covers all integer points from l_i to r_i and has a value w_i.

You are asked to select a subset of these segments (possibly, all of them). Once the subset is selected, it's possible to travel between two integer points if there exists a selected segment that covers both of them. A subset is good if it's possible to reach point m starting from point 1 in arbitrary number of moves.

The cost of the subset is the difference between the maximum and the minimum values of segments in it. Find the minimum cost of a good subset.

In every test there exists at least one good subset.

Input

The first line contains two integers n and m (1 ≤ n ≤ 3 ⋅ 10^5; 2 ≤ m ≤ 10^6) — the number of segments and the number of integer points.

Each of the next n lines contains three integers l_i, r_i and w_i (1 ≤ l_i < r_i ≤ m; 1 ≤ w_i ≤ 10^6) — the description of the i-th segment.

In every test there exists at least one good subset.

Output

Print a single integer — the minimum cost of a good subset.

Examples

Input


5 12
1 5 5
3 4 10
4 10 6
11 12 5
10 12 3


Output


3


Input


1 10
1 10 23


Output


0

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
struct debug {
  ~debug() { cerr << endl; }
  template <class c>
  debug& operator<<(c x) {
    cerr << x;
    return *this;
  }
  template <class c, class d>
  debug& operator<<(pair<c, d> x) {
    *this << "(" << x.first << ", " << x.second << ")";
    return *this;
  }
  template <class c>
  debug& operator<<(vector<c> x) {
    *this << "[";
    int f = 0;
    for (auto it : x) {
      *this << (f ? ", " : "");
      *this << it;
      f = 1;
    }
    *this << "]";
    return *this;
  }
};
struct segment {
  int l, r, w;
  segment(int _l, int _r, int _w) : l(_l), r(_r), w(_w) {}
  bool operator<(const segment& other) const { return w < other.w; }
};
int M = 2e6;
vector<int> segTree(4 * M);
vector<int> lazy(4 * M);
void push(int idx) {
  segTree[2 * idx] += lazy[idx];
  segTree[2 * idx + 1] += lazy[idx];
  segTree[idx] = min(segTree[2 * idx], segTree[2 * idx + 1]);
  lazy[2 * idx] += lazy[idx];
  lazy[2 * idx + 1] += lazy[idx];
  lazy[idx] = 0;
}
void update(int ul, int ur, int val, int idx = 1, int l = 1, int r = M) {
  if (ul > ur) return;
  if (ul == l && ur == r) {
    if (l != r) {
      lazy[idx] += val;
      push(idx);
    } else {
      segTree[idx] += val;
    }
    return;
  }
  push(idx);
  int mid = (l + r) / 2;
  update(ul, min(ur, mid), val, 2 * idx, l, mid);
  update(max(ul, mid + 1), ur, val, 2 * idx + 1, mid + 1, r);
  segTree[idx] = min(segTree[2 * idx], segTree[2 * idx + 1]);
}
int getMin(int ql, int qr, int idx = 1, int l = 1, int r = M) {
  if (ql > qr) return 1e9;
  if (ql == l && qr == r) {
    if (l != r) {
      push(idx);
    }
    return segTree[idx];
  }
  push(idx);
  int mid = (l + r) / 2;
  return min(getMin(ql, min(mid, qr), 2 * idx, l, mid),
             getMin(max(ql, mid + 1), qr, 2 * idx + 1, mid + 1, r));
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  M = 2 * m;
  vector<segment> v;
  for (int i = 0; i < n; i++) {
    int l, r, w;
    scanf("%d%d%d", &l, &r, &w);
    v.push_back(segment(2 * l, 2 * r, w));
  }
  sort(v.begin(), v.end());
  int ans = 1e9;
  int lP = 0;
  update(v[0].l, v[0].r, 1);
  if (getMin(2, 2 * m) == 1) ans = 0;
  for (int i = 1; i < n; i++) {
    update(v[i].l, v[i].r, 1);
    while (lP <= i) {
      update(v[lP].l, v[lP].r, -1);
      if (getMin(2, 2 * m) == 0) {
        update(v[lP].l, v[lP].r, 1);
        break;
      }
      lP++;
    }
    if (getMin(2, 2 * m) >= 1) {
      ans = min(ans, v[i].w - v[lP].w);
    }
  }
  printf("%d\n", ans);
}

```