#include <bits/stdc++.h>
template <typename T>
class SegmentTree {
 private:
  struct TreeNode {
    T value;
    T min_value;
    bool needs_push;
  };
  std::vector<TreeNode> data_;
  size_t size;
  void push(size_t i) {
    if (data_[i].needs_push) {
      data_[i * 2 + 1].value = data_[i].value;
      data_[i * 2 + 1].min_value = data_[i].value;
      data_[i * 2 + 1].needs_push = true;
      data_[i * 2 + 2].value = data_[i].value;
      data_[i * 2 + 2].min_value = data_[i].value;
      data_[i * 2 + 2].needs_push = true;
      data_[i].needs_push = false;
    }
  }
  void RangeUpdate(size_t i, size_t tree_left, size_t tree_right, size_t left,
                   size_t right, T value) {
    if (left >= tree_right || right <= tree_left) {
      return;
    } else if (left <= tree_left && right >= tree_right) {
      data_[i].value = value;
      data_[i].min_value = value;
      data_[i].needs_push = true;
    } else {
      push(i);
      size_t tree_mid = (tree_left + tree_right) / 2;
      RangeUpdate(i * 2 + 1, tree_left, tree_mid, left, right, value);
      RangeUpdate(i * 2 + 2, tree_mid, tree_right, left, right, value);
      data_[i].min_value =
          std::min(data_[i * 2 + 1].min_value, data_[i * 2 + 2].min_value);
    }
  }
  T RangeMin(size_t i, size_t tree_left, size_t tree_right, size_t left,
             size_t right) {
    if (left <= tree_left && right >= tree_right) {
      return data_[i].min_value;
    } else {
      push(i);
      size_t tree_mid = (tree_left + tree_right) / 2;
      if (tree_mid <= left) {
        return RangeMin(i * 2 + 2, tree_mid, tree_right, left, right);
      } else if (tree_mid >= right) {
        return RangeMin(i * 2 + 1, tree_left, tree_mid, left, right);
      } else {
        return std::min(RangeMin(i * 2 + 2, tree_mid, tree_right, left, right),
                        RangeMin(i * 2 + 1, tree_left, tree_mid, left, right));
      }
    }
  }

 public:
  SegmentTree(size_t size, T default_value) : size(size) {
    data_.resize(size * 4, TreeNode{default_value, default_value, false});
  }
  void Update(size_t left, size_t right, T value) {
    RangeUpdate(0, 0, size, left, right, value);
  }
  T GetMin(size_t left, size_t right) {
    return RangeMin(0, 0, size, left, right);
  }
};
void Solve() {
  int n = 0, m = 0, left = 0, right = 0, weight = 0;
  long long ans = 1e12, cur_min = 0;
  std::cin >> n >> m;
  std::vector<std::tuple<int, size_t, size_t>> segments;
  SegmentTree<int> tree(m * 2, -1);
  for (int i = 0; i < n; ++i) {
    std::cin >> left >> right >> weight;
    segments.emplace_back(weight, (left - 1) * 2, right * 2 - 1);
  }
  std::sort(segments.begin(), segments.end());
  for (const auto& segment : segments) {
    tree.Update(std::get<1>(segment), std::get<2>(segment),
                std::get<0>(segment));
    cur_min = tree.GetMin(0, m * 2 - 1);
    if (cur_min > -1) {
      ans = std::min(ans, std::get<0>(segment) - cur_min);
    }
  }
  std::cout << ans << '\n';
}
int main() { Solve(); }

### 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>
template <typename T>
class SegmentTree {
 private:
  struct TreeNode {
    T value;
    T min_value;
    bool needs_push;
  };
  std::vector<TreeNode> data_;
  size_t size;
  void push(size_t i) {
    if (data_[i].needs_push) {
      data_[i * 2 + 1].value = data_[i].value;
      data_[i * 2 + 1].min_value = data_[i].value;
      data_[i * 2 + 1].needs_push = true;
      data_[i * 2 + 2].value = data_[i].value;
      data_[i * 2 + 2].min_value = data_[i].value;
      data_[i * 2 + 2].needs_push = true;
      data_[i].needs_push = false;
    }
  }
  void RangeUpdate(size_t i, size_t tree_left, size_t tree_right, size_t left,
                   size_t right, T value) {
    if (left >= tree_right || right <= tree_left) {
      return;
    } else if (left <= tree_left && right >= tree_right) {
      data_[i].value = value;
      data_[i].min_value = value;
      data_[i].needs_push = true;
    } else {
      push(i);
      size_t tree_mid = (tree_left + tree_right) / 2;
      RangeUpdate(i * 2 + 1, tree_left, tree_mid, left, right, value);
      RangeUpdate(i * 2 + 2, tree_mid, tree_right, left, right, value);
      data_[i].min_value =
          std::min(data_[i * 2 + 1].min_value, data_[i * 2 + 2].min_value);
    }
  }
  T RangeMin(size_t i, size_t tree_left, size_t tree_right, size_t left,
             size_t right) {
    if (left <= tree_left && right >= tree_right) {
      return data_[i].min_value;
    } else {
      push(i);
      size_t tree_mid = (tree_left + tree_right) / 2;
      if (tree_mid <= left) {
        return RangeMin(i * 2 + 2, tree_mid, tree_right, left, right);
      } else if (tree_mid >= right) {
        return RangeMin(i * 2 + 1, tree_left, tree_mid, left, right);
      } else {
        return std::min(RangeMin(i * 2 + 2, tree_mid, tree_right, left, right),
                        RangeMin(i * 2 + 1, tree_left, tree_mid, left, right));
      }
    }
  }

 public:
  SegmentTree(size_t size, T default_value) : size(size) {
    data_.resize(size * 4, TreeNode{default_value, default_value, false});
  }
  void Update(size_t left, size_t right, T value) {
    RangeUpdate(0, 0, size, left, right, value);
  }
  T GetMin(size_t left, size_t right) {
    return RangeMin(0, 0, size, left, right);
  }
};
void Solve() {
  int n = 0, m = 0, left = 0, right = 0, weight = 0;
  long long ans = 1e12, cur_min = 0;
  std::cin >> n >> m;
  std::vector<std::tuple<int, size_t, size_t>> segments;
  SegmentTree<int> tree(m * 2, -1);
  for (int i = 0; i < n; ++i) {
    std::cin >> left >> right >> weight;
    segments.emplace_back(weight, (left - 1) * 2, right * 2 - 1);
  }
  std::sort(segments.begin(), segments.end());
  for (const auto& segment : segments) {
    tree.Update(std::get<1>(segment), std::get<2>(segment),
                std::get<0>(segment));
    cur_min = tree.GetMin(0, m * 2 - 1);
    if (cur_min > -1) {
      ans = std::min(ans, std::get<0>(segment) - cur_min);
    }
  }
  std::cout << ans << '\n';
}
int main() { Solve(); }

```