#include <bits/stdc++.h>
using namespace std;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a * b / gcd(a, b); }
struct node {
  long long lb, rb, ans = 0, lazy = 0;
  node *l, *r;
  node(long long lq, long long rq) {
    lb = lq;
    rb = rq;
    if (lb + 1 < rb) {
      long long mid = (lb + rb) / 2;
      l = new node(lb, mid);
      r = new node(mid, rb);
    }
  }
  void update() {
    if (lb + 1 < rb) ans = min(l->ans, r->ans);
  }
  void push() {
    ans += lazy;
    if (lb + 1 < rb) {
      l->lazy += lazy;
      r->lazy += lazy;
    }
    lazy = 0;
  }
  void add(long long lq, long long rq, long long x) {
    push();
    if (rb <= lq || rq < lb) return;
    if (lq <= lb && rb - 1 <= rq) {
      lazy += x;
      push();
      return;
    } else {
      l->add(lq, rq, x);
      r->add(lq, rq, x);
      update();
    }
  }
  long long minim(long long lq, long long rq) {
    push();
    if (rb <= lq || rq < lb) return LLONG_MAX;
    if (lq <= lb && rb - 1 <= rq)
      return ans;
    else
      return min(l->minim(lq, rq), r->minim(lq, rq));
  }
};
struct interval {
  long long l, r, w;
};
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n, m;
  cin >> n >> m;
  vector<interval> order(n);
  for (auto &i : order) cin >> i.l >> i.r >> i.w;
  for (auto &i : order) {
    i.r--;
  }
  sort((order).begin(), (order).end(),
       [](interval a, interval b) { return a.w < b.w; });
  node d(0, m);
  long long ans = LLONG_MAX, j = 0;
  for (long long i = 0; i < n; i++) {
    while (j < n && d.minim(1, m - 1) == 0) {
      d.add(order[j].l, order[j].r, 1);
      j++;
    }
    if (d.minim(1, m - 1) > 0) ans = min(ans, order[j - 1].w - order[i].w);
    d.add(order[i].l, order[i].r, -1);
  }
  cout << ans;
  return 0;
}

### Prompt

Please provide a Cpp coded solution 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 namespace std;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a * b / gcd(a, b); }
struct node {
  long long lb, rb, ans = 0, lazy = 0;
  node *l, *r;
  node(long long lq, long long rq) {
    lb = lq;
    rb = rq;
    if (lb + 1 < rb) {
      long long mid = (lb + rb) / 2;
      l = new node(lb, mid);
      r = new node(mid, rb);
    }
  }
  void update() {
    if (lb + 1 < rb) ans = min(l->ans, r->ans);
  }
  void push() {
    ans += lazy;
    if (lb + 1 < rb) {
      l->lazy += lazy;
      r->lazy += lazy;
    }
    lazy = 0;
  }
  void add(long long lq, long long rq, long long x) {
    push();
    if (rb <= lq || rq < lb) return;
    if (lq <= lb && rb - 1 <= rq) {
      lazy += x;
      push();
      return;
    } else {
      l->add(lq, rq, x);
      r->add(lq, rq, x);
      update();
    }
  }
  long long minim(long long lq, long long rq) {
    push();
    if (rb <= lq || rq < lb) return LLONG_MAX;
    if (lq <= lb && rb - 1 <= rq)
      return ans;
    else
      return min(l->minim(lq, rq), r->minim(lq, rq));
  }
};
struct interval {
  long long l, r, w;
};
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n, m;
  cin >> n >> m;
  vector<interval> order(n);
  for (auto &i : order) cin >> i.l >> i.r >> i.w;
  for (auto &i : order) {
    i.r--;
  }
  sort((order).begin(), (order).end(),
       [](interval a, interval b) { return a.w < b.w; });
  node d(0, m);
  long long ans = LLONG_MAX, j = 0;
  for (long long i = 0; i < n; i++) {
    while (j < n && d.minim(1, m - 1) == 0) {
      d.add(order[j].l, order[j].r, 1);
      j++;
    }
    if (d.minim(1, m - 1) > 0) ans = min(ans, order[j - 1].w - order[i].w);
    d.add(order[i].l, order[i].r, -1);
  }
  cout << ans;
  return 0;
}

```