#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int t[maxn * 4];
int b[maxn * 4];
void pushup(int rt) { t[rt] = min(t[rt << 1], t[rt << 1 | 1]); }
void update(int L, int R, int l, int r, int rt, int val) {
  if (L <= l && r <= R) {
    t[rt] += val;
    b[rt] += val;
    return;
  }
  int mid = (l + r) >> 1;
  if (b[rt] && l != r) {
    b[rt << 1] += b[rt];
    b[rt << 1 | 1] += b[rt];
    t[rt << 1] += b[rt];
    t[rt << 1 | 1] += b[rt];
    b[rt] = 0;
  }
  if (mid >= L) {
    update(L, R, l, mid, rt << 1, val);
  }
  if (mid < R) {
    update(L, R, mid + 1, r, rt << 1 | 1, val);
  }
  pushup(rt);
}
int query(int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    return t[rt];
  }
  int mid = (l + r) >> 1;
  int ans = 1e6;
  if (b[rt] && l != r) {
    b[rt << 1] += b[rt];
    b[rt << 1 | 1] += b[rt];
    t[rt << 1] += b[rt];
    t[rt << 1 | 1] += b[rt];
    b[rt] = 0;
  }
  if (mid >= L) {
    ans = min(query(L, R, l, mid, rt << 1), ans);
  }
  if (mid < R) {
    ans = min(query(L, R, mid + 1, r, rt << 1 | 1), ans);
  }
  return ans;
}
struct line {
  int l, r, w;
  bool operator<(const line &a) const { return w < a.w; }
} li[300040];
int main() {
  ios::sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> li[i].l >> li[i].r >> li[i].w;
  }
  sort(li, li + n);
  int ans = 1e8;
  queue<line> q;
  for (int i = 0; i < n; i++) {
    int w = li[i].w;
    update(li[i].l, li[i].r - 1, 1, m, 1, 1);
    q.push(li[i]);
    while (query(1, m - 1, 1, m, 1) > 0) {
      line t = q.front();
      ans = min(ans, w - t.w);
      update(t.l, t.r - 1, 1, m, 1, -1);
      q.pop();
    }
  }
  cout << ans << endl;
  return 0;
}

### Prompt

In cpp, your task is to solve 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;
const int maxn = 1e6 + 10;
int t[maxn * 4];
int b[maxn * 4];
void pushup(int rt) { t[rt] = min(t[rt << 1], t[rt << 1 | 1]); }
void update(int L, int R, int l, int r, int rt, int val) {
  if (L <= l && r <= R) {
    t[rt] += val;
    b[rt] += val;
    return;
  }
  int mid = (l + r) >> 1;
  if (b[rt] && l != r) {
    b[rt << 1] += b[rt];
    b[rt << 1 | 1] += b[rt];
    t[rt << 1] += b[rt];
    t[rt << 1 | 1] += b[rt];
    b[rt] = 0;
  }
  if (mid >= L) {
    update(L, R, l, mid, rt << 1, val);
  }
  if (mid < R) {
    update(L, R, mid + 1, r, rt << 1 | 1, val);
  }
  pushup(rt);
}
int query(int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    return t[rt];
  }
  int mid = (l + r) >> 1;
  int ans = 1e6;
  if (b[rt] && l != r) {
    b[rt << 1] += b[rt];
    b[rt << 1 | 1] += b[rt];
    t[rt << 1] += b[rt];
    t[rt << 1 | 1] += b[rt];
    b[rt] = 0;
  }
  if (mid >= L) {
    ans = min(query(L, R, l, mid, rt << 1), ans);
  }
  if (mid < R) {
    ans = min(query(L, R, mid + 1, r, rt << 1 | 1), ans);
  }
  return ans;
}
struct line {
  int l, r, w;
  bool operator<(const line &a) const { return w < a.w; }
} li[300040];
int main() {
  ios::sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> li[i].l >> li[i].r >> li[i].w;
  }
  sort(li, li + n);
  int ans = 1e8;
  queue<line> q;
  for (int i = 0; i < n; i++) {
    int w = li[i].w;
    update(li[i].l, li[i].r - 1, 1, m, 1, 1);
    q.push(li[i]);
    while (query(1, m - 1, 1, m, 1) > 0) {
      line t = q.front();
      ans = min(ans, w - t.w);
      update(t.l, t.r - 1, 1, m, 1, -1);
      q.pop();
    }
  }
  cout << ans << endl;
  return 0;
}

```