#include <bits/stdc++.h>
using namespace std;
using lli = long long int;
using vb = vector<bool>;
using vc = vector<char>;
using vd = vector<double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vlli = vector<lli>;
using vvlli = vector<vlli>;
using pi = pair<int, int>;
using plli = pair<lli, lli>;
int readint() {
  int q;
  scanf("%d", &q);
  return q;
}
lli readlong() {
  lli q;
  scanf("%lld", &q);
  return q;
}
double readdbl() {
  double q;
  scanf("%lf", &q);
  return q;
}
char readc() {
  char q;
  scanf("%c", &q);
  return q;
}
void printint(int q) { printf("%d", q); }
void printlong(lli q) { printf("%lld", q); }
void printdbl(double q, int p = 6) { printf("%.*lf", p, q); }
void readln() { scanf("\n"); }
void println() { printf("\n"); }
void space() { printf(" "); }
void print(int q) { printint(q); }
void print(lli q) { printlong(q); }
void print(double q) { printdbl(q); }
void print(char c) { printf("%c", c); }
template <typename T>
void println(T q) {
  print(q);
  println();
}
template <typename T>
void printsp(T q) {
  print(q);
  space();
}
template <typename T>
T maxim(T f, T s) {
  return (f > s) ? f : s;
}
template <typename T>
T minim(T f, T s) {
  return (f < s) ? f : s;
}
template <typename T>
T abs(T arg) {
  return arg < 0 ? -arg : arg;
}
const lli mod = 998244353;
map<int, vector<pi>> segm;
const int N = 1e6 + 1;
int n, m;
int t[2 * N];
int h;
int d[N];
void apply(int p, int value) {
  t[p] += value;
  if (p < m) d[p] += value;
}
void build(int p) {
  while (p > 1) p >>= 1, t[p] = minim(t[p << 1], t[p << 1 | 1]) + d[p];
}
void push(int p) {
  for (int s = h; s > 0; --s) {
    int i = p >> s;
    if (d[i] != 0) {
      apply(i << 1, d[i]);
      apply(i << 1 | 1, d[i]);
      d[i] = 0;
    }
  }
}
void inc(int l, int r, int value) {
  l += m, r += m;
  int l0 = l, r0 = r;
  for (; l < r; l >>= 1, r >>= 1) {
    if (l & 1) apply(l++, value);
    if (r & 1) apply(--r, value);
  }
  build(l0);
  build(r0 - 1);
}
int query(int l, int r) {
  l += m, r += m;
  push(l);
  push(r - 1);
  int res = t[l];
  for (; l < r; l >>= 1, r >>= 1) {
    if (l & 1) res = minim(res, t[l++]);
    if (r & 1) res = minim(t[--r], res);
  }
  return res;
}
int main() {
  n = readint();
  m = readint();
  h = sizeof(int) * 8 - __builtin_clz(m);
  for (int i = 0; i < n; ++i) {
    int l = readint() - 1;
    int r = readint() - 1;
    int w = readint();
    segm[w].push_back(make_pair(l, r));
  }
  vi w;
  for (auto x : segm) w.push_back(x.first);
  int res = *w.rbegin() - *w.begin();
  auto top = -1;
  auto bottom = 0;
  while (top < int(w.size()) - 1) {
    {
      do {
        top++;
        for (auto s : segm[w[top]]) {
          inc(s.first, s.second, 1);
        }
      } while (query(0, m - 1) == 0 && top < int(w.size()) - 1);
      if (query(0, m - 1) > 0) {
        res = minim(res, w[top] - w[bottom]);
        do {
          for (auto s : segm[w[bottom]]) {
            inc(s.first, s.second, -1);
          }
          bottom++;
          if (query(0, m - 1) > 0) res = minim(res, w[top] - w[bottom]);
        } while (query(0, m - 1) > 0 && top - bottom + 1 > 0);
      } else
        break;
    }
  }
  println(res);
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 lli = long long int;
using vb = vector<bool>;
using vc = vector<char>;
using vd = vector<double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vlli = vector<lli>;
using vvlli = vector<vlli>;
using pi = pair<int, int>;
using plli = pair<lli, lli>;
int readint() {
  int q;
  scanf("%d", &q);
  return q;
}
lli readlong() {
  lli q;
  scanf("%lld", &q);
  return q;
}
double readdbl() {
  double q;
  scanf("%lf", &q);
  return q;
}
char readc() {
  char q;
  scanf("%c", &q);
  return q;
}
void printint(int q) { printf("%d", q); }
void printlong(lli q) { printf("%lld", q); }
void printdbl(double q, int p = 6) { printf("%.*lf", p, q); }
void readln() { scanf("\n"); }
void println() { printf("\n"); }
void space() { printf(" "); }
void print(int q) { printint(q); }
void print(lli q) { printlong(q); }
void print(double q) { printdbl(q); }
void print(char c) { printf("%c", c); }
template <typename T>
void println(T q) {
  print(q);
  println();
}
template <typename T>
void printsp(T q) {
  print(q);
  space();
}
template <typename T>
T maxim(T f, T s) {
  return (f > s) ? f : s;
}
template <typename T>
T minim(T f, T s) {
  return (f < s) ? f : s;
}
template <typename T>
T abs(T arg) {
  return arg < 0 ? -arg : arg;
}
const lli mod = 998244353;
map<int, vector<pi>> segm;
const int N = 1e6 + 1;
int n, m;
int t[2 * N];
int h;
int d[N];
void apply(int p, int value) {
  t[p] += value;
  if (p < m) d[p] += value;
}
void build(int p) {
  while (p > 1) p >>= 1, t[p] = minim(t[p << 1], t[p << 1 | 1]) + d[p];
}
void push(int p) {
  for (int s = h; s > 0; --s) {
    int i = p >> s;
    if (d[i] != 0) {
      apply(i << 1, d[i]);
      apply(i << 1 | 1, d[i]);
      d[i] = 0;
    }
  }
}
void inc(int l, int r, int value) {
  l += m, r += m;
  int l0 = l, r0 = r;
  for (; l < r; l >>= 1, r >>= 1) {
    if (l & 1) apply(l++, value);
    if (r & 1) apply(--r, value);
  }
  build(l0);
  build(r0 - 1);
}
int query(int l, int r) {
  l += m, r += m;
  push(l);
  push(r - 1);
  int res = t[l];
  for (; l < r; l >>= 1, r >>= 1) {
    if (l & 1) res = minim(res, t[l++]);
    if (r & 1) res = minim(t[--r], res);
  }
  return res;
}
int main() {
  n = readint();
  m = readint();
  h = sizeof(int) * 8 - __builtin_clz(m);
  for (int i = 0; i < n; ++i) {
    int l = readint() - 1;
    int r = readint() - 1;
    int w = readint();
    segm[w].push_back(make_pair(l, r));
  }
  vi w;
  for (auto x : segm) w.push_back(x.first);
  int res = *w.rbegin() - *w.begin();
  auto top = -1;
  auto bottom = 0;
  while (top < int(w.size()) - 1) {
    {
      do {
        top++;
        for (auto s : segm[w[top]]) {
          inc(s.first, s.second, 1);
        }
      } while (query(0, m - 1) == 0 && top < int(w.size()) - 1);
      if (query(0, m - 1) > 0) {
        res = minim(res, w[top] - w[bottom]);
        do {
          for (auto s : segm[w[bottom]]) {
            inc(s.first, s.second, -1);
          }
          bottom++;
          if (query(0, m - 1) > 0) res = minim(res, w[top] - w[bottom]);
        } while (query(0, m - 1) > 0 && top - bottom + 1 > 0);
      } else
        break;
    }
  }
  println(res);
  return 0;
}

```