Problem: Emuskald was hired to design an artificial waterfall according to the latest trends in landscape architecture. A modern artificial waterfall consists of multiple horizontal panels affixed to a wide flat wall. The water flows down the top of the wall from panel to panel until it reaches the bottom of the wall.

The wall has height t and has n panels on the wall. Each panel is a horizontal segment at height hi which begins at li and ends at ri. The i-th panel connects the points (li, hi) and (ri, hi) of the plane. The top of the wall can be considered a panel connecting the points ( - 109, t) and (109, t). Similarly, the bottom of the wall can be considered a panel connecting the points ( - 109, 0) and (109, 0). No two panels share a common point.

Emuskald knows that for the waterfall to be aesthetically pleasing, it can flow from panel i to panel j (<image>) only if the following conditions hold: 

  1. max(li, lj) < min(ri, rj) (horizontal projections of the panels overlap); 
  2. hj < hi (panel j is below panel i); 
  3. there is no such panel k (hj < hk < hi) that the first two conditions hold for the pairs (i, k) and (k, j). 



Then the flow for <image> is equal to min(ri, rj) - max(li, lj), the length of their horizontal projection overlap.

Emuskald has decided that in his waterfall the water will flow in a single path from top to bottom. If water flows to a panel (except the bottom of the wall), the water will fall further to exactly one lower panel. The total amount of water flow in the waterfall is then defined as the minimum horizontal projection overlap between two consecutive panels in the path of the waterfall. Formally: 

  1. the waterfall consists of a single path of panels <image>; 
  2. the flow of the waterfall is the minimum flow in the path <image>. 



To make a truly great waterfall Emuskald must maximize this water flow, but there are too many panels and he is having a hard time planning his creation. Below is an example of a waterfall Emuskald wants:

<image>

Help Emuskald maintain his reputation and find the value of the maximum possible water flow.

Input

The first line of input contains two space-separated integers n and t (1 ≤ n ≤ 105, 2 ≤ t ≤ 109), the number of the panels excluding the top and the bottom panels, and the height of the wall. Each of the n following lines contain three space-separated integers hi, li and ri (0 < hi < t,  - 109 ≤ li < ri ≤ 109), the height, left and right ends of the i-th panel segment.

It is guaranteed that no two segments share a common point.

Output

Output a single integer — the maximum possible amount of water flow in the desired waterfall.

Examples

Input

5 6
4 1 6
3 2 7
5 9 11
3 10 15
1 13 16


Output

4


Input

6 5
4 2 8
3 1 2
2 2 3
2 6 12
1 0 7
1 8 11


Output

2

Note

The first test case corresponds to the picture.

Solution (in JAVA):

Solution:
import java.util.NavigableSet;
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.Collection;
import java.io.IOException;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.AbstractSet;
import java.util.NoSuchElementException;
import java.util.TreeSet;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author ogiekako
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		MyScanner in = new MyScanner(inputStream);
		MyPrintWriter out = new MyPrintWriter(outputStream);
		TaskD solver = new TaskD();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskD {
    class Segment implements Comparable<Segment>{
        final int height;
        final int left, right;
        int flow;

        public Segment(int height, int left, int right) {
            this.height = height;
            this.left = left;
            this.right = right;
        }

        public int compareTo(Segment o) {
            int tmp = IntegerUtils.compare(height, o.height);
            return tmp==0 ? IntegerUtils.compare(left, o.left) : tmp;
        }

        public String toString() {
            return "Segment{" +
                    "flow=" + flow +
                    ", height=" + height +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }
    class Part extends Interval{

        private final Segment segment;

        /**
         * if left > right, right is set as left.
         *
         * @param left  - left (inclusive)
         * @param right - right (exclusive)
         */
        public Part(long left, long right, Segment segment) {
            super(left, right);
            this.segment = segment;
        }

        public int nextFlow(Part other) {
            int overlap = (int) intersection(other).length();
            return Math.min(overlap, segment.flow);
        }
    }

    public void solve(int testNumber, MyScanner in, MyPrintWriter out) {
        int n = in.nextInt(), t = in.nextInt();
        int[] heights = new int[n], lefts = new int[n], rights= new int[n];
        for (int i = 0; i < n; i++){
            heights[i] = in.nextInt(); lefts[i] = in.nextInt(); rights[i] = in.nextInt();
        }
        long result = solve(heights, lefts, rights);
        out.println(result);
    }

    private long solve(int[] heights, int[] lefts, int[] rights){
        int n = heights.length;
        Segment[] segments = new Segment[n+2];
        for (int i = 0; i < n + 2; i++){
            segments[i] = i==0 ? new Segment(0, Integer.MIN_VALUE+1, Integer.MAX_VALUE-1) : i==n+1 ? new Segment(Integer.MAX_VALUE,Integer.MIN_VALUE+2, Integer.MAX_VALUE-2) : new Segment(heights[i-1], lefts[i-1], rights[i-1]);
        }
        Arrays.sort(segments);
        segments[0].flow = Integer.MAX_VALUE;
        TreeSet<Part> set = new TreeSet<Part>();
        set.add(new Part(segments[0].left, segments[0].right, segments[0]));
        for (int i = 1; i < segments.length; i++){
//            debug(set);
            Segment curSegment = segments[i];
            Part curPart = new Part(curSegment.left, curSegment.right, curSegment);
            Part leftPart = set.lower(new Part(curSegment.left, Integer.MAX_VALUE, curSegment));
            Part rightPart = set.lower(new Part(curSegment.right, curSegment.right, curSegment));
            if(leftPart == null)throw new AssertionError();
            if(rightPart == null)throw new AssertionError();
            NavigableSet<Part> midParts = set.subSet(leftPart, false, rightPart, false);
            curSegment.flow = 0;
            if(leftPart == rightPart)curSegment.flow = Math.max(curSegment.flow, leftPart.nextFlow(curPart));
            if(leftPart.right == leftPart.segment.right)curSegment.flow = Math.max(curSegment.flow, leftPart.nextFlow(curPart));
            if(rightPart.left == rightPart.segment.left)curSegment.flow = Math.max(curSegment.flow, rightPart.nextFlow(curPart));
            for(Part part : midParts){
                if(part.left == part.segment.left && part.right == part.segment.right){
                    long overlap = part.intersection(curPart).length();
                    curSegment.flow = (int) Math.max(curSegment.flow, Math.min(overlap, part.segment.flow));
                }
            }
            set.remove(leftPart);
            set.remove(rightPart);
            set.removeAll(new TreeSet<Part>(midParts));
            Part nLeftPart = new Part(leftPart.left, curPart.left, leftPart.segment);
            Part nRightPart = new Part(curPart.right, rightPart.right, rightPart.segment);
            set.add(curPart);
            if(nLeftPart.length() > 0)set.add(nLeftPart);
            if(nRightPart.length() > 0)set.add(nRightPart);
        }
//        debug(set);
        return segments[n+1].flow;
    }

//    public static void main(String[] args) {
//        Random rnd = new Random(124089124L);
//        int n = 3;
//        int t = 1000;
//        for (int i = 0; i < 1000000; i++){
//            int[] heights = new int[n];
//            int[] lefts = new int[n], rights = new int[n];
//            for (int j = 0; j < n; j++){
//                heights[j] = rnd.nextInt(t-1) + 1;
//                lefts[j] = rnd.nextInt(10);
//                rights[j] = rnd.nextInt(10);
//                if(lefts[j]==rights[j]){
//                    j--;continue;
//                }
//                if(lefts[j] > rights[j]){int tmp = lefts[j]; lefts[j] = rights[j]; rights[j] = tmp;}
//            }
//            long res = new TaskD().solve(heights,lefts, rights);
//            long exp = solveStupid(heights, lefts, rights);
//            if(res!=exp){
//                debug(heights);
//                debug(lefts);
//                debug(rights);
//                debug(exp, res);
//                throw new AssertionError();
//            }
//        }
//    }
//
//    private static long solveStupid(int[] _heights, int[] _lefts, int[] _rights) {
//        int _n = _heights.length;
//        int n = _n + 2;
//        long[] heights = new long[n], lefts = new long[n], rights = new long[n];
//        for (int i = 0; i < n; i++){
//            heights[i] = i==0 ? 0 : i==n-1 ? Integer.MAX_VALUE : _heights[i-1];
//            lefts[i] = i==0 || i==n-1 ? Integer.MIN_VALUE : _lefts[i-1];
//            rights[i] = i==0 || i==n-1 ? Integer.MAX_VALUE : _rights[i-1];
//        }
//        boolean[][] valid = new boolean[n][n];
//        for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)valid[i][j] = heights[i] < heights[j] && Math.max(lefts[i], lefts[j]) < Math.min(rights[i], rights[j]);
//        long[][] capacity = new long[n][n];// i -> j
//        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)if(valid[i][j]){
//            capacity[i][j] = Math.min(rights[i], rights[j]) - Math.max(lefts[i], lefts[j]);
//            for (int k = 0; k < n; k++)if(valid[i][k] && valid[k][j])capacity[i][j] = 0;
//        }
//        long[] dp = new long[n];
//        dp[0] = Integer.MAX_VALUE;
//        boolean[] visited = new boolean[n];
//        visited[0] = true;
//        for (int i = 0; i < n-1; i++){
//            int p = -1;
//            for (int j = 0; j < n; j++)if(!visited[j] &&(p==-1 || heights[p] > heights[j]))p = j;
//            visited[p] = true;
//            for (int j = 0; j < n; j++)if(visited[j])dp[p] = Math.max(dp[p], Math.min(dp[j], capacity[j][p]));
//        }
//        return dp[n-1];
//    }
//
//    static void debug(Object...os){
//        System.err.println(Arrays.deepToString(os));
//    }
}

class IntegerUtils {

    public static int compare(long o1, long o2) {
        return o1 < o2 ? -1 : o1 > o2 ? 1 : 0;
    }

    }

class Interval implements Comparable<Interval>{
    public final long left,right;

    /**
     * if left > right, right is set as left.
     * @param left - left (inclusive)
     * @param right - right (exclusive)
     */
    public Interval(long left, long right) {// [left, right)
        if(left > right)right = left;
        this.left = left;
        this.right = right;
    }

    public int compareTo(Interval o) {
        if(left != o.left)return IntegerUtils.compare(left, o.left);
        return IntegerUtils.compare(right, o.right);
    }

    public long length() {
        return right - left;
    }

    /*
     * returns an empty(0-length) interval when the intersection is empty.
     */
    public Interval intersection(Interval interval){
        long nLeft = Math.max(left, interval.left);
        long nRight = Math.min(right, interval.right);
        if(nLeft < nRight)return new Interval(nLeft,nRight);
        return new Interval(nLeft,nLeft);
    }

    public String toString() {
        return "Interval{" +
                "left=" + left +
                ", right=" + right +
                '}';
    }
}

class MyScanner {
    private final InputStream in;

    public MyScanner(InputStream in) {
        this.in = in;
    }

    int bufLen;
    int bufPtr;
    byte[] buf = new byte[1024];

    public int read() {
        if (bufLen == -1)
            throw new InputMismatchException();
        if (bufPtr >= bufLen) {
            bufPtr = 0;
            try {
                bufLen = in.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (bufLen <= 0)
                return -1;
        }
        return buf[bufPtr++];
    }

    public int nextInt() {
        int c = read();
        if (c == -1) throw new NoSuchElementException();
        while (c != '-' && (c < '0' || '9' < c)) {
            c = read();
            if (c == -1) throw new NoSuchElementException();
        }
        if (c == '-') return -nextInt();
        int res = 0;
        do {
            res *= 10;
            res += c - '0';
            c = read();
        } while ('0' <= c && c <= '9');
        return res;
    }


    }

class MyPrintWriter {
    PrintWriter out;

    public MyPrintWriter(OutputStream outputStream) {
        out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public MyPrintWriter(Writer writer) {
        out = new PrintWriter(writer);
    }

    public void println(Object... os) {
        for (int i = 0; i < os.length - 1; i++) {
            out.print(os[i]);
            out.print(' ');
        }
        out.println(os[os.length - 1]);
    }

    public void close() {
        out.close();
    }

    }