#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
template <typename T>
void etch(T V) {
  for (auto x : V) cout << x << ' ';
  cout << '\n';
}
vector<string> vec_splitter(string s) {
  s += ',';
  vector<string> res;
  while (!s.empty()) {
    res.push_back(s.substr(0, s.find(',')));
    s = s.substr(s.find(',') + 1);
  }
  return res;
}
void debug_out(vector<string> __attribute__((unused)) args,
               __attribute__((unused)) long long int idx,
               __attribute__((unused)) long long int LINE_NUM) {
  cerr << endl;
}
template <typename Head, typename... Tail>
void debug_out(vector<string> args, long long int idx, long long int LINE_NUM,
               Head H, Tail... T) {
  if (idx > 0)
    cerr << ", ";
  else
    cerr << "Line(" << LINE_NUM << ") ";
  stringstream ss;
  ss << H;
  cerr << args[idx] << " = " << ss.str();
  debug_out(args, idx + 1, LINE_NUM, T...);
}
const long long int MOD = 1e9 + 7;
const long long int MOD1 = 998244353;
const long long int N = 2e5 + 5;
const long long int INF = 1000111000111000111LL;
const long double EPS = 1e-12;
const long double PI = 3.141592653589793116;
struct seg_tree {
  vector<long long int> bit;
  vector<long long int> a;
  vector<long long int> lazy;
  long long int n;
  seg_tree(long long int n) {
    this->n = n;
    bit.assign(4 * n + 5, 0);
    lazy.assign(4 * n + 5, 0);
  }
  seg_tree(vector<long long int> a) : seg_tree(a.size()) {
    this->a = a;
    build(0, 0, (long long int)a.size() - 1);
  }
  long long int merge(long long int x, long long int y) { return min(x, y); }
  void build(long long int node, long long int start, long long int end) {
    if (start == end) {
      bit[node] = a[start];
      return;
    }
    long long int lch = 2 * node + 1;
    long long int rch = 2 * node + 2;
    long long int mid = (start + end) / 2;
    build(lch, start, mid);
    build(rch, mid + 1, end);
    bit[node] = merge(bit[lch], bit[rch]);
    return;
  }
  void push(long long int v) {
    bit[v * 2 + 1] += lazy[v];
    lazy[v * 2 + 1] += lazy[v];
    bit[v * 2 + 2] += lazy[v];
    lazy[v * 2 + 2] += lazy[v];
    lazy[v] = 0;
  }
  void update(long long int v, long long int tl, long long int tr,
              long long int l, long long int r, long long int addend) {
    if (l > r) return;
    if (l == tl && tr == r) {
      bit[v] += addend;
      lazy[v] += addend;
    } else {
      push(v);
      long long int tm = (tl + tr) / 2;
      update(v * 2 + 1, tl, tm, l, min(r, tm), addend);
      update(v * 2 + 2, tm + 1, tr, max(l, tm + 1), r, addend);
      bit[v] = merge(bit[v * 2 + 1], bit[v * 2 + 2]);
    }
  }
  long long int query(long long int v, long long int tl, long long int tr,
                      long long int l, long long int r) {
    if (l > r) return 1;
    if (l <= tl && tr <= r) return bit[v];
    push(v);
    long long int tm = (tl + tr) / 2;
    return merge(query(v * 2 + 1, tl, tm, l, min(r, tm)),
                 query(v * 2 + 2, tm + 1, tr, max(l, tm + 1), r));
  }
};
struct edge {
  long long int l, r, w;
};
bool comp(edge a, edge b) { return a.w < b.w; }
int32_t main() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int n, m;
  cin >> n >> m;
  m--;
  vector<edge> v(n);
  vector<long long int> a(m + 1, 0);
  for (auto &x : v) {
    cin >> x.l >> x.r >> x.w;
    x.r--;
  }
  long long int ans = INF;
  sort((v).begin(), (v).end(), comp);
  seg_tree sg(a);
  long long int l = 0, r = 1;
  sg.update(0, 0, m, v[0].l, v[0].r, 1);
  while (l < n) {
    while (r < n && !sg.query(0, 0, m, 1, m)) {
      sg.update(0, 0, m, v[r].l, v[r].r, 1);
      r++;
    }
    if (sg.query(0, 0, m, 1, m)) {
      ans = min(ans, v[r - 1].w - v[l].w);
    }
    sg.update(0, 0, m, v[l].l, v[l].r, -1);
    l++;
  }
  cout << ans;
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
template <typename T>
void etch(T V) {
  for (auto x : V) cout << x << ' ';
  cout << '\n';
}
vector<string> vec_splitter(string s) {
  s += ',';
  vector<string> res;
  while (!s.empty()) {
    res.push_back(s.substr(0, s.find(',')));
    s = s.substr(s.find(',') + 1);
  }
  return res;
}
void debug_out(vector<string> __attribute__((unused)) args,
               __attribute__((unused)) long long int idx,
               __attribute__((unused)) long long int LINE_NUM) {
  cerr << endl;
}
template <typename Head, typename... Tail>
void debug_out(vector<string> args, long long int idx, long long int LINE_NUM,
               Head H, Tail... T) {
  if (idx > 0)
    cerr << ", ";
  else
    cerr << "Line(" << LINE_NUM << ") ";
  stringstream ss;
  ss << H;
  cerr << args[idx] << " = " << ss.str();
  debug_out(args, idx + 1, LINE_NUM, T...);
}
const long long int MOD = 1e9 + 7;
const long long int MOD1 = 998244353;
const long long int N = 2e5 + 5;
const long long int INF = 1000111000111000111LL;
const long double EPS = 1e-12;
const long double PI = 3.141592653589793116;
struct seg_tree {
  vector<long long int> bit;
  vector<long long int> a;
  vector<long long int> lazy;
  long long int n;
  seg_tree(long long int n) {
    this->n = n;
    bit.assign(4 * n + 5, 0);
    lazy.assign(4 * n + 5, 0);
  }
  seg_tree(vector<long long int> a) : seg_tree(a.size()) {
    this->a = a;
    build(0, 0, (long long int)a.size() - 1);
  }
  long long int merge(long long int x, long long int y) { return min(x, y); }
  void build(long long int node, long long int start, long long int end) {
    if (start == end) {
      bit[node] = a[start];
      return;
    }
    long long int lch = 2 * node + 1;
    long long int rch = 2 * node + 2;
    long long int mid = (start + end) / 2;
    build(lch, start, mid);
    build(rch, mid + 1, end);
    bit[node] = merge(bit[lch], bit[rch]);
    return;
  }
  void push(long long int v) {
    bit[v * 2 + 1] += lazy[v];
    lazy[v * 2 + 1] += lazy[v];
    bit[v * 2 + 2] += lazy[v];
    lazy[v * 2 + 2] += lazy[v];
    lazy[v] = 0;
  }
  void update(long long int v, long long int tl, long long int tr,
              long long int l, long long int r, long long int addend) {
    if (l > r) return;
    if (l == tl && tr == r) {
      bit[v] += addend;
      lazy[v] += addend;
    } else {
      push(v);
      long long int tm = (tl + tr) / 2;
      update(v * 2 + 1, tl, tm, l, min(r, tm), addend);
      update(v * 2 + 2, tm + 1, tr, max(l, tm + 1), r, addend);
      bit[v] = merge(bit[v * 2 + 1], bit[v * 2 + 2]);
    }
  }
  long long int query(long long int v, long long int tl, long long int tr,
                      long long int l, long long int r) {
    if (l > r) return 1;
    if (l <= tl && tr <= r) return bit[v];
    push(v);
    long long int tm = (tl + tr) / 2;
    return merge(query(v * 2 + 1, tl, tm, l, min(r, tm)),
                 query(v * 2 + 2, tm + 1, tr, max(l, tm + 1), r));
  }
};
struct edge {
  long long int l, r, w;
};
bool comp(edge a, edge b) { return a.w < b.w; }
int32_t main() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int n, m;
  cin >> n >> m;
  m--;
  vector<edge> v(n);
  vector<long long int> a(m + 1, 0);
  for (auto &x : v) {
    cin >> x.l >> x.r >> x.w;
    x.r--;
  }
  long long int ans = INF;
  sort((v).begin(), (v).end(), comp);
  seg_tree sg(a);
  long long int l = 0, r = 1;
  sg.update(0, 0, m, v[0].l, v[0].r, 1);
  while (l < n) {
    while (r < n && !sg.query(0, 0, m, 1, m)) {
      sg.update(0, 0, m, v[r].l, v[r].r, 1);
      r++;
    }
    if (sg.query(0, 0, m, 1, m)) {
      ans = min(ans, v[r - 1].w - v[l].w);
    }
    sg.update(0, 0, m, v[l].l, v[l].r, -1);
    l++;
  }
  cout << ans;
  return 0;
}

```