human
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
Using python3 can you solve the prior task?

=====
Write me a Python program to find the minimum cost of a good subset?
assistant
#Here is Python program to find the minimum cost of a good subset.

import io,os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline


class segment_tree(object):

    def merge(self,num,minimum):
        return min(minimum,num)

    def __init__(self,n,initial):
        self.n = (n+1)
        self.arr = [0]*(2*n+2)
        self.lazy = [0]*(n+1)
        self.layer = n.bit_length() + 1

        for i in range(2*n,n,-1):
            self.arr[i] = initial[i-n-1]

        for i in range(n-1,-1,-1):
            self.arr[i] = self.merge(self.arr[2*i],self.arr[2*i+1])


    def rebuild(self,index):
        index = index >> 1
        while index>0:
            self.arr[index] = self.merge(self.arr[index<<1],self.arr[index<<1|1]) + self.lazy[index]
            index = index >> 1
        


    def update(self,left,right,target):
        i,j = self.n+left, self.n+right+1
        i0,j0 = i,j
        while i<j:
            if i&1:
                self.arr[i] += target
                if i<self.n:  self.lazy[i] += target
                i += 1
            if j&1:
                j -= 1
                self.arr[j] += target
                if j<self.n:  self.lazy[j] += target
            i = i >> 1
            j = j >> 1

#        if i==j:
#            self.arr[i] += target
#            if j<self.n:  self.lazy[i] += target
 
        self.rebuild(i0)
        self.rebuild(j0)

    def pushdown(self,index):
        for move in range(self.layer,0,-1):
            father = index >> move
            if father<1 or father>=self.n: continue 
            if self.lazy[father]==0: continue 
            child = father << 1
            self.arr[child] += self.lazy[father]
            self.arr[child+1] += self.lazy[father]
            
            if child < self.n:  self.lazy[child] += self.lazy[father]
            if child+1 < self.n:  self.lazy[child+1] += self.lazy[father]
            self.lazy[father] = 0


                           



    def query(self,left,right):
        i,j = self.n+left,  self.n+right+1

        output = 2147483647  # initial output should be changed if...