Problem: Pavel is going to make a game of his dream. However, he knows that he can't make it on his own so he founded a development company and hired n workers of staff. Now he wants to pick n workers from the staff who will be directly responsible for developing a game.

Each worker has a certain skill level vi. Besides, each worker doesn't want to work with the one whose skill is very different. In other words, the i-th worker won't work with those whose skill is less than li, and with those whose skill is more than ri.

Pavel understands that the game of his dream isn't too hard to develop, so the worker with any skill will be equally useful. That's why he wants to pick a team of the maximum possible size. Help him pick such team.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the number of workers Pavel hired.

Each of the following n lines contains three space-separated integers li, vi, ri (1 ≤ li ≤ vi ≤ ri ≤ 3·105) — the minimum skill value of the workers that the i-th worker can work with, the i-th worker's skill and the maximum skill value of the workers that the i-th worker can work with.

Output

In the first line print a single integer m — the number of workers Pavel must pick for developing the game.

In the next line print m space-separated integers — the numbers of the workers in any order.

If there are multiple optimal solutions, print any of them.

Examples

Input

4
2 8 9
1 4 7
3 6 8
5 8 10


Output

3
1 3 4


Input

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


Output

4
1 2 3 5

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class DevelopingGame {
    
    private static final int MAXV = 524288;
    
    private static class Worker {
        int l, r, v;
    }
    
    int n;
    
    Worker[] workers;
    
    int bestl, bestr, best;
    
    private void input() throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String str = reader.readLine();
        String ss[] = str.split(" ");
        n = Integer.valueOf(ss[0]);
        workers = new Worker[n];
        for (int i = 0; i < n; i++) {
            str = reader.readLine();
            ss = str.split(" ");
            workers[i] = new Worker();
            workers[i].l = Integer.valueOf(ss[0]);
            workers[i].v = Integer.valueOf(ss[1]);
            workers[i].r = Integer.valueOf(ss[2]);
        }
    }
    
    private static class Node {
        int cover, max, maxp;
    }
    
    private static class Result {
        int max, maxp;
    }
    
    private static class Point {
        boolean isIn;
        double v;
        int p;
    }
    
    private void changeNodeCover(Node node, int v) {
        node.cover += v;
        node.max += v;
    }
    
    private void updateMaxp(Node[] tree, int p) {
        int pl = p*2 + 1;
        int pr = p*2 + 2;
        if (tree[pl].max < tree[pr].max) {
            tree[p].max = tree[pr].max + tree[p].cover;
            tree[p].maxp = tree[pr].maxp;
        } else {
            tree[p].max = tree[pl].max + tree[p].cover;
            tree[p].maxp = tree[pl].maxp;
        }
    }
    
    private void insert(Node[] tree, int p, int l, int r, int l1, int r1, int v) {
        if (l1 == l && r1 == r) {
            changeNodeCover(tree[p], v);
            return ;
        }
        int mid = (l+r)>>1;
        int pl = p*2+1;
        int pr = p*2+2;
        if (l1 <= mid) {
            if (r1 <= mid) insert(tree, pl, l, mid, l1, r1, v); else {
                insert(tree, pl, l, mid, l1, mid, v);
                insert(tree, pr, mid+1, r, mid+1, r1, v);
            }
        } else {
            insert(tree, pr, mid+1, r, l1, r1, v);
        }
        if (tree[pl].cover < 0 || tree[pr].cover < 0) {
            changeNodeCover(tree[pl], 1);
            changeNodeCover(tree[pr], 1);
            changeNodeCover(tree[p], -1);
        }
        if (tree[pl].cover > 0 && tree[pr].cover > 0) {
            changeNodeCover(tree[p], 1);
            changeNodeCover(tree[pl], -1);
            changeNodeCover(tree[pr], -1);
        }
        updateMaxp(tree, p);
    }
    
    private Result findMax(Node[] tree, int p, int l, int r, int l1, int r1) {
        Result result;
        if (l1 == l && r1 == r) {
            result = new Result();
            result.max = tree[p].max;
            result.maxp = tree[p].maxp;
            return result;
        }
        int mid = (l+r)>>1;
        int pl = p*2+1;
        int pr = p*2+2;
        if (l1 <= mid) {
            if (r1 <= mid) {
                result = findMax(tree, pl, l, mid, l1, r1);
            } else {
                Result result1 = findMax(tree, pl, l, mid, l1, mid);
                Result result2 = findMax(tree, pr, mid+1, r, mid+1, r1);
                if (result1.max < result2.max) result = result2;
                else result = result1;
            }
        } else {
            result = findMax(tree, pr, mid+1, r, l1, r1);
        }
        result.max += tree[p].cover;
        return result;
    }
    
    private void build(Node[] tree, int p, int l, int r) {
        tree[p] = new Node();
        tree[p].max = 0;
        tree[p].maxp = l;
        if (l < r) {
            int mid = (l+r)>>1;
            build(tree, p*2+1, l, mid);
            build(tree, p*2+2, mid + 1, r);
        }
    }
        
    private void solve() {
        Point points[] = new Point[n*2];
        for (int i = 0; i < n; i++) {
            points[i] = new Point();
            points[i].isIn = true;
            points[i].v = workers[i].v;
            points[i].p = i;
            points[i+n] = new Point();
            points[i+n].isIn = false;
            points[i+n].v = workers[i].r + 0.1;
            points[i+n].p = i;
        }
        Arrays.sort(points, new Comparator<Point>() {
            public int compare(Point p1, Point p2) {
                if (p1.v < p2.v) return -1;
                if (p1.v > p2.v) return 1;
                return 0;
            }
        });
        Node[] tree = new Node[MAXV*2+1];
        build(tree, 0, 1, 300000);
        bestl = bestr = best = 0;
        for (int i = 0; i < 2*n; i++) {
            Worker w = workers[points[i].p];
            if (points[i].isIn) {
                insert(tree, 0, 1, 300000, w.l, w.v, 1);
                Result result = findMax(tree, 0, 1, 300000, 1, w.v);
                if (result.max > best) {
                    best = result.max;
                    bestl = result.maxp;
                    bestr = w.v;
                }
            }
            else {
                insert(tree, 0, 1, 300000, w.l, w.v, -1);
            }
        }
    }
    
    private void output() {
        StringBuilder result = new StringBuilder();
        result.append(best).append('\n');
        for (int i = 0; i < n; i++) {
            if (workers[i].l <= bestl && workers[i].r >= bestr && workers[i].v >= bestl && workers[i].v <= bestr) {
                result.append(i+1).append(' ');
            }
        }
        System.out.println(result.toString());
    }
    
    public static void main(String[] args) throws Exception {
        DevelopingGame d = new DevelopingGame();
        d.input();
        d.solve();
        d.output();
    }

}