1555_E. Boring Segments_148
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 java.util.*;
import java.io.*;

public class BoringSegments {
    static int m;
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out,false);
        int n = scanner.nextInt();
        m = scanner.nextInt();
        Seg[] segs = new Seg[n];
        for(int i = 0; i < n; i++) {
            segs[i] = new Seg(scanner.nextInt()-1, scanner.nextInt()-2, scanner.nextInt());
        }
        Arrays.sort(segs, new Comparator<Seg>() {
            public int compare(Seg o1, Seg o2) {
                return o1.w - o2.w;
            }
        });
        out.println(comp(segs));
        out.flush();
    }
    static int comp(Seg[] segs) {
        int l = 0;
        SegTree sg = new SegTree(m-1, 0, m-2);
        int ans = 10000006;
        for(int i = 0; i < segs.length; i++) {
            //System.out.println("Adding: " + segs[i].l + " " + segs[i].r + " " + segs[i].w);
            sg.update(1,segs[i].l, segs[i].r, 1);
            while(sg.minimum(1,0, m-2) > 0) {
                ans = Math.min(ans, segs[i].w-segs[l].w);
                //System.out.println("Removing: " + segs[l].l + " " + segs[l].r + " " + segs[l].w);
                sg.update(1,segs[l].l, segs[l].r, -1);
                l++;
            }
        }
        return ans;
    }
    static class SegTree {
        int[] hi, lo, min, delta;
        public SegTree(int ss, int l, int r) {
            hi = new int[4 * ss + 1];
            lo = new int[4 * ss + 1];
            delta = new int[4 * ss + 1];
            min = new int[4 * ss + 1];
            init(1, l, r);
        }
        void init(int cur, int l, int r) {
            hi[cur] = r;
            lo[cur] = l;
            int mid = ( l + r)/2;
            if ( l == r) return;
            init(cur * 2, l, mid);
            init(cur * 2 + 1, mid + 1, r);
        }
        void prop(int cur) {
            delta[cur * 2] += delta[cur];
            delta[cur*2 + 1] += delta[cur];
            delta[cur] = 0;
        }
        void update(int cur) {
            min[cur] = Math.min(min[cur*2] + delta[cur * 2], min[cur * 2 + 1] + delta[cur*2 + 1]);
        }
        void update(int cur, int l, int r, int amt) {
            if (hi[cur] < l || lo[cur] > r) return;
            if (hi[cur] <= r && lo[cur] >= l) {
                delta[cur] += amt;
                return;
            }
            prop(cur);
            update(cur * 2, l, r, amt);
            update(cur*2 +1, l, r, amt);
            update(cur);
        }
        int minimum(int cur, int l, int r) {
            if (hi[cur] < l || lo[cur] > r) return Integer.MAX_VALUE;
            if (hi[cur] <= r && lo[cur] >= l) {
                return min[cur] + delta[cur];
            }
            prop(cur);
            int lmin = minimum(cur * 2, l, r);
            int rmin = minimum(cur * 2 + 1, l, r);
            update(cur);
            return Math.min(lmin, rmin);
        }
    }
    static class Seg {
        int l,r,w;
        public Seg(int ll, int rr, int ww) {
            l = ll; r = rr; w =ww;
        }
    }
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}
