1555_E. Boring Segments_147
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
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 addtarget(self,index,target):
        self.arr[index] += target
        if index<self.n:  self.lazy[index] += target


    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.addtarget(i,target)
                i += 1
            if j&1:
                j -= 1
                self.addtarget(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 you want to change the merge function

        self.pushdown(i)
        self.pushdown(j)


        while i<j:
            if i&1:
                output = self.merge(self.arr[i],output)
                i += 1
            if j&1:
                j -= 1
                output = self.merge(self.arr[j],output)
            i = i >> 1
            j = j >> 1

        return output



                           








def main(t):


    n,m = map(int,input().split())
    segments = []
    for _ in range(n):
        front,rear,w = map(int,input().split())
        segments.append([w,front-1,rear-1])

    segments = sorted(segments)


    over = segment_tree(m-1,[0]*(m-1))


    front = 0
    ans = 2147483647
    flag = False


    for i in range(n):

#        print(i)

        over.update(segments[i][1],segments[i][2]-1,1)



        if not flag and over.query(0,m-2)>0:
            flag = True

        if flag:
            while over.query( segments[front][1], segments[front][2] - 1) > 1:
                front += 1
                over.update(segments[front-1][1],segments[front-1][2]-1,-1)



#                for p in range(segments[front-1][1],segments[front-1][2]):
#                    over.addnum(p,-1)

            ans = min(ans,segments[i][0]-segments[front][0])
       
         


    print(ans)




















T = 1
t = 1
while t<=T:
    main(t)
    t += 1

