#include <bits/stdc++.h>
using namespace std;
long long mod = 1e9 + 7;
int mxn = 1e6 + 7, INF = 1e9;
int n, m;
vector<long long> a, t, lazy;
void build(int v, int tl, int tr) {
  if (tl == tr) {
    t[v] = a[tl];
  } else {
    int tm = (tl + tr) / 2;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
  }
}
void push(int v) {
  t[v * 2] += lazy[v];
  lazy[v * 2] += lazy[v];
  t[v * 2 + 1] += lazy[v];
  lazy[v * 2 + 1] += lazy[v];
  lazy[v] = 0;
}
void update(int v, int tl, int tr, int l, int r, int addend) {
  if (l > r) return;
  if (l == tl && tr == r) {
    t[v] += addend;
    lazy[v] += addend;
  } else {
    push(v);
    int tm = (tl + tr) / 2;
    update(v * 2, tl, tm, l, min(r, tm), addend);
    update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, addend);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
  }
}
int query(int v, int tl, int tr, int l, int r) {
  if (l > r) {
    return INF;
  }
  if (l <= tl && tr <= r) {
    return t[v];
  }
  push(v);
  int tm = (tl + tr) / 2;
  return min(query(v * 2, tl, tm, l, min(r, tm)),
             query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}
void fix() {
  mxn = m + 10;
  a.assign(mxn, 0ll);
  t.assign(4 * mxn, INF);
  lazy.assign(4 * mxn, 0ll);
}
int ans = 1e9;
struct data {
  int l, r, w;
} p[1000000];
bool compare(struct data &d1, struct data &d2) {
  if (d2.w != d1.w) {
    return d2.w > d1.w;
  } else if (d2.l != d1.l) {
    return d2.l > d1.l;
  } else {
    return d2.r > d1.r;
  }
}
void solve() {
  cin >> n >> m;
  fix();
  for (int i = 0; i < n; i++) {
    int l, r, w;
    cin >> l >> r >> w;
    r--;
    p[i].l = l;
    p[i].r = r;
    p[i].w = w;
  }
  sort(p, p + n, compare);
  build(1, 0, m - 1);
  int i = 0, j = -1;
  while (i < n) {
    bool ok = 0;
    while (query(1, 0, m - 1, 1, m - 1) <= 0) {
      j++;
      if (j >= n) {
        ok = 1;
        break;
      }
      update(1, 0, m - 1, p[j].l, p[j].r, 1);
    }
    if (ok) break;
    ans = min(ans, p[j].w - p[i].w);
    update(1, 0, m - 1, p[i].l, p[i].r, -1);
    i++;
  }
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int T = 1;
  while (T--) {
    solve();
  }
  return 0;
}

### Prompt

Generate a cpp solution to 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;
long long mod = 1e9 + 7;
int mxn = 1e6 + 7, INF = 1e9;
int n, m;
vector<long long> a, t, lazy;
void build(int v, int tl, int tr) {
  if (tl == tr) {
    t[v] = a[tl];
  } else {
    int tm = (tl + tr) / 2;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
  }
}
void push(int v) {
  t[v * 2] += lazy[v];
  lazy[v * 2] += lazy[v];
  t[v * 2 + 1] += lazy[v];
  lazy[v * 2 + 1] += lazy[v];
  lazy[v] = 0;
}
void update(int v, int tl, int tr, int l, int r, int addend) {
  if (l > r) return;
  if (l == tl && tr == r) {
    t[v] += addend;
    lazy[v] += addend;
  } else {
    push(v);
    int tm = (tl + tr) / 2;
    update(v * 2, tl, tm, l, min(r, tm), addend);
    update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, addend);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
  }
}
int query(int v, int tl, int tr, int l, int r) {
  if (l > r) {
    return INF;
  }
  if (l <= tl && tr <= r) {
    return t[v];
  }
  push(v);
  int tm = (tl + tr) / 2;
  return min(query(v * 2, tl, tm, l, min(r, tm)),
             query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}
void fix() {
  mxn = m + 10;
  a.assign(mxn, 0ll);
  t.assign(4 * mxn, INF);
  lazy.assign(4 * mxn, 0ll);
}
int ans = 1e9;
struct data {
  int l, r, w;
} p[1000000];
bool compare(struct data &d1, struct data &d2) {
  if (d2.w != d1.w) {
    return d2.w > d1.w;
  } else if (d2.l != d1.l) {
    return d2.l > d1.l;
  } else {
    return d2.r > d1.r;
  }
}
void solve() {
  cin >> n >> m;
  fix();
  for (int i = 0; i < n; i++) {
    int l, r, w;
    cin >> l >> r >> w;
    r--;
    p[i].l = l;
    p[i].r = r;
    p[i].w = w;
  }
  sort(p, p + n, compare);
  build(1, 0, m - 1);
  int i = 0, j = -1;
  while (i < n) {
    bool ok = 0;
    while (query(1, 0, m - 1, 1, m - 1) <= 0) {
      j++;
      if (j >= n) {
        ok = 1;
        break;
      }
      update(1, 0, m - 1, p[j].l, p[j].r, 1);
    }
    if (ok) break;
    ans = min(ans, p[j].w - p[i].w);
    update(1, 0, m - 1, p[i].l, p[i].r, -1);
    i++;
  }
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int T = 1;
  while (T--) {
    solve();
  }
  return 0;
}

```