#include <bits/stdc++.h>
using namespace std;
struct segTree {
  int l, r;
  long long sum;
  long long tag;
  segTree *ls, *rs;
  segTree(int _l, int _r) {
    l = _l, r = _r;
    ls = rs = nullptr;
    sum = tag = 0;
  }
  inline void update(long long val) {
    tag += val;
    sum += val;
  }
  void pushDown() {
    if (ls == nullptr) {
      int m = l + r >> 1;
      ls = new segTree(l, m);
      rs = new segTree(m, r);
    }
    if (tag) {
      ls->update(tag);
      rs->update(tag);
      tag = 0;
    }
  }
  void pushUp() { sum = min(ls->sum, rs->sum); }
  void update(int L, int R, long long val) {
    if (L <= l and R >= r) {
      update(val);
    } else if (R <= l or r <= L) {
      return;
    } else {
      pushDown();
      ls->update(L, R, val);
      rs->update(L, R, val);
      pushUp();
    }
  }
  long long query(int L, int R) {
    if (L <= l and R >= r) {
      return sum;
    } else if (R <= l or r <= L) {
      return 1e18;
    } else {
      pushDown();
      return min(ls->query(L, R), rs->query(L, R));
    }
  }
  void init() {
    if (r - l == 1) {
      sum = 0;
    } else {
      pushDown();
      ls->init();
      rs->init();
      pushUp();
    }
  }
};
struct seg {
  long long c;
  int l, r;
  bool operator<(const seg &s) const { return c < s.c; }
};
int main() {
  int n, m;
  cin >> n >> m;
  vector<seg> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i].l >> s[i].r >> s[i].c;
  }
  segTree cover(1, m);
  sort(s.begin(), s.end());
  long long ans = 1e18;
  int r = 0;
  for (int i = 0; i < s.size(); i++) {
    while (!cover.query(1, m)) {
      if (r >= n) {
        cout << ans;
        return 0;
      }
      cover.update(s[r].l, s[r].r, 1);
      r++;
    }
    ans = min(ans, s[r - 1].c - s[i].c);
    cover.update(s[i].l, s[i].r, -1);
  }
  cout << ans;
  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;
struct segTree {
  int l, r;
  long long sum;
  long long tag;
  segTree *ls, *rs;
  segTree(int _l, int _r) {
    l = _l, r = _r;
    ls = rs = nullptr;
    sum = tag = 0;
  }
  inline void update(long long val) {
    tag += val;
    sum += val;
  }
  void pushDown() {
    if (ls == nullptr) {
      int m = l + r >> 1;
      ls = new segTree(l, m);
      rs = new segTree(m, r);
    }
    if (tag) {
      ls->update(tag);
      rs->update(tag);
      tag = 0;
    }
  }
  void pushUp() { sum = min(ls->sum, rs->sum); }
  void update(int L, int R, long long val) {
    if (L <= l and R >= r) {
      update(val);
    } else if (R <= l or r <= L) {
      return;
    } else {
      pushDown();
      ls->update(L, R, val);
      rs->update(L, R, val);
      pushUp();
    }
  }
  long long query(int L, int R) {
    if (L <= l and R >= r) {
      return sum;
    } else if (R <= l or r <= L) {
      return 1e18;
    } else {
      pushDown();
      return min(ls->query(L, R), rs->query(L, R));
    }
  }
  void init() {
    if (r - l == 1) {
      sum = 0;
    } else {
      pushDown();
      ls->init();
      rs->init();
      pushUp();
    }
  }
};
struct seg {
  long long c;
  int l, r;
  bool operator<(const seg &s) const { return c < s.c; }
};
int main() {
  int n, m;
  cin >> n >> m;
  vector<seg> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i].l >> s[i].r >> s[i].c;
  }
  segTree cover(1, m);
  sort(s.begin(), s.end());
  long long ans = 1e18;
  int r = 0;
  for (int i = 0; i < s.size(); i++) {
    while (!cover.query(1, m)) {
      if (r >= n) {
        cout << ans;
        return 0;
      }
      cover.update(s[r].l, s[r].r, 1);
      r++;
    }
    ans = min(ans, s[r - 1].c - s[i].c);
    cover.update(s[i].l, s[i].r, -1);
  }
  cout << ans;
  return 0;
}

```