1557_D. Ezzat and Grid_188
Moamen was drawing a grid of n rows and 10^9 columns containing only digits 0 and 1. Ezzat noticed what Moamen was drawing and became interested in the minimum number of rows one needs to remove to make the grid beautiful.

A grid is beautiful if and only if for every two consecutive rows there is at least one column containing 1 in these two rows.

Ezzat will give you the number of rows n, and m segments of the grid that contain digits 1. Every segment is represented with three integers i, l, and r, where i represents the row number, and l and r represent the first and the last column of the segment in that row.

For example, if n = 3, m = 6, and the segments are (1,1,1), (1,7,8), (2,7,7), (2,15,15), (3,1,1), (3,15,15), then the grid is:

<image>

Your task is to tell Ezzat the minimum number of rows that should be removed to make the grid beautiful.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 3⋅10^5).

Each of the next m lines contains three integers i, l, and r (1 ≤ i ≤ n, 1 ≤ l ≤ r ≤ 10^9). Each of these m lines means that row number i contains digits 1 in columns from l to r, inclusive.

Note that the segments may overlap.

Output

In the first line, print a single integer k — the minimum number of rows that should be removed.

In the second line print k distinct integers r_1, r_2, …, r_k, representing the rows that should be removed (1 ≤ r_i ≤ n), in any order.

If there are multiple answers, print any.

Examples

Input


3 6
1 1 1
1 7 8
2 7 7
2 15 15
3 1 1
3 15 15


Output


0


Input


5 4
1 2 3
2 4 6
3 3 5
5 1 1


Output


3
2 4 5

Note

In the first test case, the grid is the one explained in the problem statement. The grid has the following properties: 

  1. The 1-st row and the 2-nd row have a common 1 in the column 7. 
  2. The 2-nd row and the 3-rd row have a common 1 in the column 15. 

As a result, this grid is beautiful and we do not need to remove any row.

In the second test case, the given grid is as follows: 

<image>
import java.io.*;
import java.util.*;

public class Main {

    private static final long MOD = 1000000007;

    static int[] readArray(int size, InputReader in, boolean subOne) {
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = in.nextInt() + (subOne ? -1 : 0);
        }
        return a;
    }

    static long[] readLongArray(int size, InputReader in) {
        long[] a = new long[size];
        for (int i = 0; i < size; i++) {
            a[i] = in.nextLong();
        }
        return a;
    }

    static void sortArray(int[] a) {
        Random random = new Random();

        for (int i = 0; i < a.length; i++) {
            int randomPos = random.nextInt(a.length);
            int t = a[i];
            a[i] = a[randomPos];
            a[randomPos] = t;
        }
        Arrays.sort(a);
    }

    public static final Comparator<long[]> PAIR_COMPARATOR = (o1, o2) -> {
        if (o1[0] == o2[0]) {
            return Long.compare(o1[1], o2[1]);
        }
        return Long.compare(o1[0], o2[0]);
    };

    public static void main(String[] args) throws FileNotFoundException {
//        InputReader in = new InputReader(new FileInputStream("input.txt"));
//        PrintWriter out = new PrintWriter(new BufferedOutputStream(new FileOutputStream("milkvisits.out")));
//
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        int n = in.nextInt();
        int m = in.nextInt();
        List<long[]> segs = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            int row = in.nextInt() - 1;
            segs.add(new long[]{in.nextLong() * 2, i, row});
            segs.add(new long[]{in.nextLong() * 2 + 1, i, row});
        }
        segs.sort(PAIR_COMPARATOR);

        int[] ans = new int[n];
        Arrays.fill(ans, 1);
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }

        TreeMap<Integer, Integer> rows = new TreeMap<>();
        for (long[] p : segs) {
            if (p[0] % 2 == 0) {
                Integer floor = rows.floorKey((int) (p[2] - 1));
                if (floor != null) {
                    graph[floor].add((int) p[2]);
                }
                Integer ceil = rows.ceilingKey((int) (p[2] + 1));
                if (ceil != null) {
                    graph[(int) p[2]].add(ceil);
                }
                if (!rows.containsKey((int) p[2])) {
                    rows.put((int) p[2], 1);
                } else {
                    rows.put((int) p[2], rows.get((int) p[2]) + 1);
                }
            } else {
                if (rows.get((int) p[2]) == 1) {
                    rows.remove((int) p[2]);
                } else {
                    rows.put((int) p[2], rows.get((int) p[2]) - 1);
                }
            }
        }

        int res = 1;
        int resInd = 0;
        int[] prev = new int[n];
        Arrays.fill(prev, -1);
        for (int i = n - 1; i >= 0; i--) {
            for (int to : graph[i]) {
                if (to > i && ans[i] < 1 + ans[to]) {
                    prev[i] = to;
                    ans[i] = 1 + ans[to];
                    if (res < ans[i]) {
                        res = ans[i];
                        resInd = i;
                    }
                }
            }
        }

        StringBuilder str = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i != resInd) {
                str.append(i + 1).append(" ");
            } else {
                resInd = prev[i];
            }
        }
        out.println(n - res);
        out.println(str);

        out.close();
    }


    private static void outputArray(int[] ans, PrintWriter out, boolean addOne) {
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < ans.length; i++) {
            long an = ans[i] + (addOne ? 1 : 0);
            str.append(an).append(' ');
        }
        out.println(str);
    }

    private static void outputArray(List<Integer> ans, PrintWriter out, boolean addOne) {
        StringBuilder str = new StringBuilder();
        for (int j = 0; j < ans.size(); j++) {
            long i = ans.get(j);
            long an = i + (addOne ? 1 : 0);
            str.append(an);
            if (j < ans.size() - 1) {
                str.append(' ');
            }
        }
        out.println(str);
//        out.flush();
    }

    private static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextString() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public char nextChar() {
            return next().charAt(0);
        }

        public String nextWord() {
            return next();
        }

        private List<Integer>[] readTree(int n) {
            return readGraph(n, n - 1);
        }

        private List<Integer>[] readGraph(int n, int m) {
            List<Integer>[] result = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                result[i] = new ArrayList<>();
            }
            for (int i = 0; i < m; i++) {
                int u = nextInt() - 1;
                int v = nextInt() - 1;
                result[u].add(v);
                result[v].add(u);
            }
            return result;
        }

        private Map<Integer, Long>[] readWeightedGraph(int n, int m) {
            Map<Integer, Long>[] result = new HashMap[n];
            for (int i = 0; i < n; i++) {
                result[i] = new HashMap<>();
            }
            for (int i = 0; i < m; i++) {
                int u = nextInt() - 1;
                int v = nextInt() - 1;
                long w = nextLong();
                result[u].put(v, Math.min(w, result[u].getOrDefault(v, Long.MAX_VALUE)));
                result[v].put(u, Math.min(w, result[v].getOrDefault(u, Long.MAX_VALUE)));
            }
            return result;
        }

    }
}