Boring Segments solution codeforces

Boring Segments solution codeforces


You are given nn segments on a number line, numbered from 11 to nn. The ii-th segments covers all integer points from lili to riri and has a value wiwi.

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 mm starting from point 11 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 nn and mm (1n31051≤n≤3⋅1052m1062≤m≤106) — the number of segments and the number of integer points.

Each of the next nn lines contains three integers liliriri and wiwi (1li<rim1≤li<ri≤m1wi1061≤wi≤106) — the description of the ii-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

Copy
5 12
1 5 5
3 4 10
4 10 6
11 12 5
10 12 3

output

Copy
3

input

Copy
1 10
1 10 23

output

Copy
0

Leave a Comment