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?
assistant
#Here is Python code 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.layer = (n-1).bit_length() 

        newn = 1 << self.layer
        self.n = newn
#        print(newn)
  

        self.arr = [2147483647]*(2*newn)
        self.lazy = [0]*(newn)

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

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

#        print(self.arr)

    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
        i0,j0 = i,j
        while i<j:

            if i&1:
                self.addtarget(i,target)
                i += 1

            if not j&1:
                self.addtarget(j,target)
                j -= 1

            i = i >> 1
            j = j >> 1

        if i==j:
            self.addtarget(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 =...