Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

sortings

trees

two pointers

*2100

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Boring Segments

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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 \le n \le 3 \cdot 10^5$$$; $$$2 \le m \le 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 \le l_i < r_i \le m$$$; $$$1 \le w_i \le 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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/14/2024 14:12:54 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|