#include <bits/stdc++.h>
using namespace std;
int n, m;
struct seg {
  int t[3000300 << 2], ad[3000300 << 2];
  inline void up(int k) { t[k] = min(t[k << 1], t[k << 1 | 1]); }
  void build(int k, int l, int r) {
    ad[k] = 0;
    if (l == r) return t[k] = 0, void();
    int m = l + r >> 1;
    build(k << 1, l, m), build(k << 1 | 1, m + 1, r);
    up(k);
  }
  inline void down(int k) {
    t[k << 1] += ad[k], t[k << 1 | 1] += ad[k];
    ad[k << 1] += ad[k], ad[k << 1 | 1] += ad[k];
    ad[k] = 0;
  }
  void cover(int k, int l, int r, int L, int R, int v) {
    if (l >= L && r <= R) {
      t[k] += v, ad[k] += v;
      return;
    }
    if (ad[k] != 0) down(k);
    int m = l + r >> 1;
    if (L <= m) cover(k << 1, l, m, L, R, v);
    if (R > m) cover(k << 1 | 1, m + 1, r, L, R, v);
    up(k);
  }
  int ask(int k, int l, int r, int L, int R) {
    if (l >= L && r <= R) return t[k];
    if (ad[k] != 0) down(k);
    int m = l + r >> 1, res = 1e9 + 7;
    if (L <= m) res = min(res, ask(k << 1, l, m, L, R));
    if (R > m) res = min(res, ask(k << 1 | 1, m + 1, r, L, R));
    return res;
  }
} T;
vector<pair<int, pair<int, int> > > L;
inline void solve() {
  int ans = 1e9 + 7;
  cin >> n >> m;
  for (auto i = (1); i <= (n); ++i) {
    int l, r, w;
    cin >> l >> r >> w;
    L.push_back({w, {l, r - 1}});
  }
  --m;
  sort(L.begin(), L.end());
  T.build(1, 1, m);
  int r = -1;
  for (auto i = (1); i <= (n); ++i) {
    while (r < n - 1 && T.t[1] == 0)
      ++r, T.cover(1, 1, m, L[r].second.first, L[r].second.second, 1);
    if (T.t[1] > 0) ans = min(ans, L[r].first - L[i - 1].first);
    T.cover(1, 1, m, L[i - 1].second.first, L[i - 1].second.second, -1);
  }
  cout << ans << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T = 1;
  while (T--) solve();
}

### Prompt

Your task is to create 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;
int n, m;
struct seg {
  int t[3000300 << 2], ad[3000300 << 2];
  inline void up(int k) { t[k] = min(t[k << 1], t[k << 1 | 1]); }
  void build(int k, int l, int r) {
    ad[k] = 0;
    if (l == r) return t[k] = 0, void();
    int m = l + r >> 1;
    build(k << 1, l, m), build(k << 1 | 1, m + 1, r);
    up(k);
  }
  inline void down(int k) {
    t[k << 1] += ad[k], t[k << 1 | 1] += ad[k];
    ad[k << 1] += ad[k], ad[k << 1 | 1] += ad[k];
    ad[k] = 0;
  }
  void cover(int k, int l, int r, int L, int R, int v) {
    if (l >= L && r <= R) {
      t[k] += v, ad[k] += v;
      return;
    }
    if (ad[k] != 0) down(k);
    int m = l + r >> 1;
    if (L <= m) cover(k << 1, l, m, L, R, v);
    if (R > m) cover(k << 1 | 1, m + 1, r, L, R, v);
    up(k);
  }
  int ask(int k, int l, int r, int L, int R) {
    if (l >= L && r <= R) return t[k];
    if (ad[k] != 0) down(k);
    int m = l + r >> 1, res = 1e9 + 7;
    if (L <= m) res = min(res, ask(k << 1, l, m, L, R));
    if (R > m) res = min(res, ask(k << 1 | 1, m + 1, r, L, R));
    return res;
  }
} T;
vector<pair<int, pair<int, int> > > L;
inline void solve() {
  int ans = 1e9 + 7;
  cin >> n >> m;
  for (auto i = (1); i <= (n); ++i) {
    int l, r, w;
    cin >> l >> r >> w;
    L.push_back({w, {l, r - 1}});
  }
  --m;
  sort(L.begin(), L.end());
  T.build(1, 1, m);
  int r = -1;
  for (auto i = (1); i <= (n); ++i) {
    while (r < n - 1 && T.t[1] == 0)
      ++r, T.cover(1, 1, m, L[r].second.first, L[r].second.second, 1);
    if (T.t[1] > 0) ans = min(ans, L[r].first - L[i - 1].first);
    T.cover(1, 1, m, L[i - 1].second.first, L[i - 1].second.second, -1);
  }
  cout << ans << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T = 1;
  while (T--) solve();
}

```