#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int n, m;
int const N = 3e5 + 2;
int const M = (1 << 21);
struct Triple {
  int fi;
  int se;
  int th;
  Triple(int f, int s, int t) : fi(f), se(s), th(t) {}
};
struct Compare {
  bool operator()(const Triple& f, const Triple& g) {
    if (f.th != g.th)
      return (f.th < g.th);
    else
      return pair<int, int>{f.fi, f.se} < pair<int, int>{g.fi, g.se};
  }
};
vector<Triple> seg;
int t[M];
int lazy[M];
int const INF = 1e9;
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;
}
int query(int v, int l, int r, int tl, int tr) {
  if (r < l) return INF;
  if (l == tl && r == tr)
    return t[v];
  else {
    push(v);
    int mid = (tl + tr) / 2;
    int qw1 = query(v * 2, l, min(mid, r), tl, mid);
    int qw2 = query(v * 2 + 1, max(mid + 1, l), r, mid + 1, tr);
    return min(qw1, qw2);
  }
}
void update(int v, int l, int r, int tl, int tr, int val) {
  if (r < l) return;
  if (l == tl && r == tr) {
    t[v] += val;
    lazy[v] += val;
  } else {
    push(v);
    int mid = (tl + tr) >> 1;
    update(v << 1, l, min(mid, r), tl, mid, val);
    update((v << 1) + 1, max(mid + 1, l), r, mid + 1, tr, val);
    t[v] = min(t[v << 1], t[(v << 1) + 1]);
  }
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = (1); i <= (n); i++) {
    int l, r, w;
    scanf("%d %d %d", &l, &r, &w);
    seg.push_back(Triple({l, r, w}));
  }
  sort(seg.begin(), seg.end(), Compare());
  int mu = 0;
  int lb = seg[0].th;
  int rb = seg[0].th;
  int ans = INF;
  for (int i = (1); i <= (n); i++) {
    update(1, seg[i - 1].fi, seg[i - 1].se - 1, 1, m - 1, 1);
    rb = seg[i - 1].th;
    while (query(1, 1, m - 1, 1, m - 1) > 0) {
      ans = min(ans, rb - lb);
      update(1, seg[mu].fi, seg[mu].se - 1, 1, m - 1, -1);
      mu++;
      if (mu != n) lb = seg[mu].th;
    }
  }
  printf("%d", ans);
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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 ll = long long;
using namespace std;
int n, m;
int const N = 3e5 + 2;
int const M = (1 << 21);
struct Triple {
  int fi;
  int se;
  int th;
  Triple(int f, int s, int t) : fi(f), se(s), th(t) {}
};
struct Compare {
  bool operator()(const Triple& f, const Triple& g) {
    if (f.th != g.th)
      return (f.th < g.th);
    else
      return pair<int, int>{f.fi, f.se} < pair<int, int>{g.fi, g.se};
  }
};
vector<Triple> seg;
int t[M];
int lazy[M];
int const INF = 1e9;
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;
}
int query(int v, int l, int r, int tl, int tr) {
  if (r < l) return INF;
  if (l == tl && r == tr)
    return t[v];
  else {
    push(v);
    int mid = (tl + tr) / 2;
    int qw1 = query(v * 2, l, min(mid, r), tl, mid);
    int qw2 = query(v * 2 + 1, max(mid + 1, l), r, mid + 1, tr);
    return min(qw1, qw2);
  }
}
void update(int v, int l, int r, int tl, int tr, int val) {
  if (r < l) return;
  if (l == tl && r == tr) {
    t[v] += val;
    lazy[v] += val;
  } else {
    push(v);
    int mid = (tl + tr) >> 1;
    update(v << 1, l, min(mid, r), tl, mid, val);
    update((v << 1) + 1, max(mid + 1, l), r, mid + 1, tr, val);
    t[v] = min(t[v << 1], t[(v << 1) + 1]);
  }
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = (1); i <= (n); i++) {
    int l, r, w;
    scanf("%d %d %d", &l, &r, &w);
    seg.push_back(Triple({l, r, w}));
  }
  sort(seg.begin(), seg.end(), Compare());
  int mu = 0;
  int lb = seg[0].th;
  int rb = seg[0].th;
  int ans = INF;
  for (int i = (1); i <= (n); i++) {
    update(1, seg[i - 1].fi, seg[i - 1].se - 1, 1, m - 1, 1);
    rb = seg[i - 1].th;
    while (query(1, 1, m - 1, 1, m - 1) > 0) {
      ans = min(ans, rb - lb);
      update(1, seg[mu].fi, seg[mu].se - 1, 1, m - 1, -1);
      mu++;
      if (mu != n) lb = seg[mu].th;
    }
  }
  printf("%d", ans);
  return 0;
}

```