Grisha come to a contest and faced the following problem.

You are given an array of size n, initially consisting of zeros. The elements of the array are enumerated from 1 to n. You perform q operations on the array. The i-th operation is described with three integers l_i, r_i and x_i (1 ≤ l_i ≤ r_i ≤ n, 1 ≤ x_i ≤ n) and means that you should add x_i to each of the elements with indices l_i, l_i + 1, …, r_i. After all operations you should find the maximum in the array.

Grisha is clever, so he solved the problem quickly.

However something went wrong inside his head and now he thinks of the following question: "consider we applied some subset of the operations to the array. What are the possible values of the maximum in the array?"

Help Grisha, find all integers y between 1 and n such that if you apply some subset (possibly empty) of the operations, then the maximum in the array becomes equal to y.

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 10^{4}) — the length of the array and the number of queries in the initial problem.

The following q lines contain queries, one per line. The i-th of these lines contains three integers l_i, r_i and x_i (1 ≤ l_i ≤ r_i ≤ n, 1 ≤ x_i ≤ n), denoting a query of adding x_i to the segment from l_i-th to r_i-th elements of the array, inclusive.

Output

In the first line print the only integer k, denoting the number of integers from 1 to n, inclusive, that can be equal to the maximum in the array after applying some subset (possibly empty) of the given operations.

In the next line print these k integers from 1 to n — the possible values of the maximum. Print these integers in increasing order.

Examples

Input

4 3
1 3 1
2 4 2
3 4 4


Output

4
1 2 3 4 


Input

7 2
1 5 1
3 7 2


Output

3
1 2 3 


Input

10 3
1 1 2
1 1 3
1 1 6


Output

6
2 3 5 6 8 9 

Note

Consider the first example. If you consider the subset only of the first query, the maximum is equal to 1. If you take only the second query, the maximum equals to 2. If you take the first two queries, the maximum becomes 3. If you take only the fourth query, the maximum becomes 4. If you take the fourth query and something more, the maximum becomes greater that n, so you shouldn't print it.

In the second example you can take the first query to obtain 1. You can take only the second query to obtain 2. You can take all queries to obtain 3.

In the third example you can obtain the following maximums:

  * You can achieve the maximim of 2 by using queries: (1). 
  * You can achieve the maximim of 3 by using queries: (2). 
  * You can achieve the maximim of 5 by using queries: (1, 2). 
  * You can achieve the maximim of 6 by using queries: (3). 
  * You can achieve the maximim of 8 by using queries: (1, 3). 
  * You can achieve the maximim of 9 by using queries: (2, 3). 
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Random;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.Comparator;
import java.io.InputStream;

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

    static class TaskE {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            long MOD = MathExtentions.getRandomPrime_suitable_as_MOD_for_long_multipling();
            int n = in.NextInt();
            int q = in.NextInt();
            int[][] segsByEnd = in.NextIntMatrix(q, 3);
            int[][] segsByStart = new int[q][];
            System.arraycopy(segsByEnd, 0, segsByStart, 0, q);
            Arrays.sort(segsByEnd, Comparator.comparingInt(o -> o[1]));
            Arrays.sort(segsByStart, Comparator.comparingInt(o -> o[0]));
            int i = 0;
            int j = 0;
            boolean[] possibilities = new boolean[n + 1];
            long[] numberOfWays = new long[n + 1];
            numberOfWays[0] = 1;
            while (i < q || j < q) {
                int ss = n + 10;
                if (i < q)
                    ss = segsByStart[i][0];
                if (j < q)
                    ss = Math.min(ss, segsByEnd[j][1] + 1);

                while (j < q && segsByEnd[j][1] + 1 == ss) {
                    for (int k = 0; k <= n - segsByEnd[j][2]; k++) {
                        numberOfWays[k + segsByEnd[j][2]] -= numberOfWays[k];
                        if (numberOfWays[k + segsByEnd[j][2]] < 0) numberOfWays[k + segsByEnd[j][2]] += MOD;
                    }
                    j++;
                }
                while (i < q && segsByStart[i][0] == ss) {
                    for (int k = n - segsByStart[i][2]; k >= 0; k--) {
                        numberOfWays[k + segsByStart[i][2]] += numberOfWays[k];
                        if (numberOfWays[k + segsByStart[i][2]] >= MOD) numberOfWays[k + segsByStart[i][2]] -= MOD;
                    }
                    i++;
                }
                for (int k = 1; k <= n; k++) {
                    possibilities[k] |= numberOfWays[k] != 0;
                }
            }
            int count = 0;
            for (int ii = 1; ii <= n; ii++) if (possibilities[ii]) count++;
            out.println(count);
            for (int k = 1; k <= n; k++) {
                if (possibilities[k]) {
                    out.print(k + " ");
                }
            }
            out.println();
        }

    }

    static class InputReader {
        BufferedReader reader;
        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(), " \t\n\r\f,");
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

        public int[][] NextIntMatrix(int n, int m) {
            return NextIntMatrix(n, m, 0);
        }

        public int[][] NextIntMatrix(int n, int m, int offset) {
            int[][] a = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    a[i][j] = NextInt() + offset;
                }
            }
            return a;
        }

    }

    static class MathExtentions {
        static Random r = new Random();
        private static int[] options = new int[]{99999989, 99999971, 99999959, 99999941, 99999931, 99999847, 99999839, 99999827, 99999821, 99999787, 99999773, 99999721, 99999703, 99999677, 99999643, 99999623, 99999617, 99999611, 99999589, 99999587, 99999563, 99999551, 99999547, 99999541, 99999539, 99999517, 99999509, 99999481, 99999439, 99999437, 99999401, 99999373, 99999353, 99999343, 99999329, 99999323, 99999307, 99999259, 99999257, 99999247, 99999217, 99999187, 99999167, 99999157, 99999131, 99999113, 99999103, 99999089, 99999079, 99999077, 99999073, 99999043, 99998999, 99998971, 99998953, 99998933, 99998929, 99998909, 99998891, 99998869, 99998851, 99998819, 99998797, 99998783, 99998749, 99998663, 99998611, 99998609, 99998603, 99998557, 99998551, 99998543, 99998513, 99998497, 99998491, 99998473, 99998449, 99998447, 99998441, 99998429, 99998417, 99998413, 99998377, 99998363, 99998357, 99998323, 99998299, 99998291, 99998257, 99998251, 99998231, 99998207, 99998191, 99998147, 99998111, 99998099, 99998071, 99998051, 99998021, 99997981, 99997973
                , 99997957, 99997949, 99997913, 99997907, 99997901, 99997897, 99997879, 99997873, 99997871, 99997867, 99997841, 99997837, 99997789, 99997783, 99997769, 99997759, 99997691, 99997687, 99997679, 99997669, 99997649, 99997619, 99997609, 99997571, 99997543, 99997531, 99997523, 99997511, 99997493, 99997459, 99997441, 99997427, 99997411, 99997393, 99997369, 99997367, 99997357, 99997267, 99997243, 99997189, 99997187, 99997159, 99997151, 99997129, 99997127, 99997081, 99997069, 99997067, 99997063, 99997033, 99996983, 99996971, 99996947, 99996931, 99996899, 99996863, 99996833, 99996821, 99996803, 99996797, 99996779, 99996769, 99996749, 99996719, 99996697, 99996691, 99996679, 99996671, 99996667, 99996653, 99996647, 99996619, 99996583, 99996577, 99996551, 99996521, 99996517, 99996511, 99996509, 99996473, 99996419, 99996409, 99996389, 99996353, 99996343, 99996317, 99996293, 99996287, 99996271, 99996257, 99996251, 99996241, 99996229, 99996191, 99996181, 99996179, 99996151, 99996139, 99996133, 99996131
                , 99996121, 99996097, 99996079, 99996077, 99996059, 99996011, 99995999, 99995983, 99995957, 99995939, 99995933, 99995923, 99995899, 99995893, 99995891, 99995869, 99995851, 99995839, 99995813, 99995807, 99995783, 99995771, 99995767, 99995747, 99995723, 99995711, 99995699, 99995681, 99995671, 99995669, 99995663, 99995647, 99995641, 99995629, 99995603, 99995591, 99995573, 99995569, 99995563, 99995551, 99995549, 99995527, 99995507, 99995453, 99995417, 99995407, 99995317, 99995303, 99995297, 99995281, 99995279, 99995267, 99995261, 99995257, 99995249, 99995227, 99995213, 99995209, 99995197, 99995177, 99995171, 99995113, 99995111, 99995087, 99995059, 99995041, 99995039, 99995011, 99994963, 99994919, 99994907, 99994883, 99994877, 99994861, 99994849, 99994819, 99994801, 99994771, 99994759, 99994751, 99994723, 99994711, 99994703, 99994691, 99994679, 99994673, 99994669, 99994637, 99994633, 99994621, 99994607, 99994579, 99994571, 99994567, 99994553, 99994481, 99994471, 99994379, 99994373, 99994361
                , 99994327, 99994319, 99994309, 99994277, 99994273, 99994267, 99994253, 99994231, 99994229, 99994211, 99994201, 99994183, 99994177, 99994157, 99994129, 99994123, 99994079, 99994073, 99994061, 99994043, 99994021, 99994009, 99993997, 99993991, 99993947, 99993923, 99993917, 99993911, 99993893, 99993889, 99993841, 99993833, 99993821, 99993799, 99993787, 99993781, 99993767, 99993743, 99993679, 99993671, 99993611, 99993601, 99993583, 99993527, 99993511, 99993497, 99993469, 99993463, 99993461, 99993449, 99993433, 99993427, 99993419, 99993407, 99993359, 99993349, 99993343, 99993331, 99993329, 99993317, 99993287, 99993281, 99993263, 99993253, 99993211, 99993199, 99993193, 99993169, 99993163, 99993161, 99993119, 99993109, 99993097, 99993071, 99993053, 99993001, 99992993, 99992947, 99992941, 99992939, 99992917, 99992911, 99992903, 99992897, 99992869, 99992843, 99992831, 99992813, 99992807, 99992803, 99992797, 99992791, 99992777, 99992773, 99992771, 99992747, 99992681, 99992671, 99992617, 99992539
                , 99992533, 99992527, 99992509, 99992483, 99992471, 99992467, 99992461, 99992449, 99992447, 99992437, 99992429, 99992413, 99992401, 99992381, 99992363, 99992311, 99992309, 99992303, 99992251, 99992239, 99992219, 99992213, 99992209, 99992173, 99992161, 99992149, 99992141, 99992119, 99992099, 99992089, 99992059, 99992051, 99992027, 99991999, 99991987, 99991981, 99991951, 99991937, 99991933, 99991901, 99991897, 99991891, 99991877, 99991831, 99991819, 99991789, 99991769, 99991757, 99991753, 99991733, 99991721, 99991687, 99991673, 99991667, 99991609, 99991583, 99991561, 99991559, 99991519, 99991517, 99991499, 99991481, 99991447, 99991387, 99991379, 99991363, 99991343, 99991303, 99991277, 99991273, 99991271, 99991249, 99991237, 99991207, 99991109, 99991103, 99991081, 99991063, 99991049, 99991033, 99991009, 99990973, 99990971, 99990967, 99990929, 99990911, 99990893, 99990887, 99990871, 99990799, 99990757, 99990739, 99990731, 99990703, 99990679, 99990647, 99990641, 99990589, 99990587, 99990581
                , 99990577, 99990571, 99990551, 99990547, 99990533, 99990511, 99990493, 99990491, 99990487, 99990467, 99990461, 99990419, 99990389, 99990337, 99990329, 99990307, 99990299, 99990287, 99990281, 99990263, 99990239, 99990181, 99990161, 99990139, 99990113, 99990091, 99990083, 99990053, 99990049, 99990043, 99990029, 99990001, 99989983, 99989963, 99989909, 99989891, 99989887, 99989863, 99989833, 99989819, 99989807, 99989803, 99989783, 99989759, 99989711, 99989683, 99989677, 99989657, 99989639, 99989627, 99989599, 99989581, 99989573, 99989569, 99989567, 99989557, 99989551, 99989543, 99989537, 99989509, 99989501, 99989497, 99989489, 99989479, 99989459, 99989423, 99989389, 99989369, 99989339, 99989333, 99989327, 99989317, 99989311, 99989269, 99989261, 99989251, 99989237, 99989209, 99989179, 99989177, 99989171, 99989159, 99989117, 99989107, 99989101, 99989093, 99989083, 99989081, 99989063, 99989051, 99989047, 99989041, 99989033, 99989023, 99989009, 99989003, 99988997, 99988961, 99988913, 99988879
                , 99988859, 99988853, 99988831, 99988829, 99988813, 99988807, 99988771, 99988753, 99988649, 99988633, 99988619, 99988597, 99988591, 99988579, 99988573, 99988571, 99988531, 99988489, 99988487, 99988481, 99988477, 99988453, 99988409, 99988403, 99988367, 99988363, 99988349, 99988331, 99988313, 99988289, 99988277, 99988261, 99988253, 99988247, 99988219, 99988139, 99988117, 99988103, 99988099, 99988073, 99988069, 99988037, 99988019, 99988003, 99987997, 99987991, 99987983, 99987973, 99987961, 99987959, 99987917, 99987907, 99987893, 99987887, 99987883, 99987871, 99987869, 99987817, 99987799, 99987787, 99987781, 99987779, 99987763, 99987721, 99987707, 99987691, 99987683, 99987619, 99987611, 99987593, 99987581, 99987571, 99987539, 99987529, 99987497, 99987467, 99987457, 99987449, 99987373, 99987343, 99987313, 99987301, 99987299, 99987281, 99987271, 99987269, 99987263, 99987257, 99987221, 99987211, 99987197, 99987161, 99987133, 99987131, 99987119, 99987103, 99987089, 99987067, 99987037, 99987011
                , 99986993, 99986989, 99986969, 99986963, 99986947, 99986933, 99986927, 99986891, 99986881, 99986857, 99986851, 99986849, 99986827, 99986801, 99986791, 99986767, 99986743, 99986723, 99986717, 99986699, 99986669, 99986657, 99986647, 99986641, 99986633, 99986629, 99986611, 99986609, 99986597, 99986539, 99986527, 99986521, 99986507, 99986489, 99986483, 99986479, 99986477, 99986449, 99986431, 99986423, 99986353, 99986351, 99986347, 99986329, 99986279, 99986273, 99986269, 99986251, 99986233, 99986153, 99986141, 99986123, 99986111, 99986093, 99986077, 99986063, 99986053, 99986039, 99986023, 99986011, 99985987, 99985973, 99985927, 99985883, 99985849, 99985843, 99985811, 99985799, 99985777, 99985727, 99985723, 99985709, 99985693, 99985681, 99985673, 99985663, 99985661, 99985651, 99985637, 99985603, 99985579, 99985573, 99985559, 99985549, 99985547, 99985489, 99985463, 99985441, 99985427, 99985423, 99985409, 99985397, 99985351, 99985339, 99985337, 99985321, 99985297, 99985273, 99985271, 99985267
                , 99985241, 99985219, 99985217, 99985159, 99985157, 99985153, 99985147, 99985141, 99985099, 99985091, 99985057, 99985021, 99985009, 99984991, 99984967, 99984947, 99984923, 99984919, 99984893, 99984883, 99984877, 99984853, 99984823, 99984817, 99984757, 99984751, 99984743, 99984733, 99984697, 99984679, 99984629, 99984623, 99984617, 99984607, 99984601, 99984587, 99984559, 99984541, 99984529, 99984491, 99984487, 99984461, 99984457, 99984449, 99984439, 99984421, 99984413, 99984383, 99984371, 99984347, 99984343, 99984337, 99984329, 99984319, 99984277, 99984271, 99984253, 99984239, 99984221, 99984211, 99984187, 99984169, 99984149, 99984133, 99984127, 99984121, 99984119, 99984109, 99984103, 99984097, 99984091, 99984043, 99984029, 99983971, 99983969, 99983957, 99983929, 99983867, 99983861, 99983837, 99983797, 99983761, 99983759, 99983753, 99983717, 99983683, 99983669, 99983633, 99983627, 99983621, 99983581, 99983573, 99983563, 99983489, 99983483, 99983459, 99983449, 99983441, 99983437, 99983431
                , 99983423, 99983419, 99983413, 99983381, 99983357, 99983353, 99983333, 99983327, 99983311, 99983309, 99983243, 99983237, 99983227, 99983207, 99983201, 99983197, 99983189, 99983183, 99983179, 99983141, 99983129, 99983119, 99983113, 99983083, 99983077, 99983057, 99983017, 99982957, 99982951, 99982943, 99982937, 99982903, 99982901, 99982889, 99982877, 99982859, 99982849, 99982811, 99982801, 99982759, 99982741, 99982717, 99982709, 99982703, 99982669, 99982643, 99982609, 99982601, 99982573, 99982537, 99982523, 99982507, 99982499, 99982483, 99982453, 99982447, 99982429, 99982417, 99982391, 99982369, 99982367, 99982339, 99982307, 99982303, 99982297, 99982261, 99982249, 99982247, 99982243, 99982241, 99982229, 99982217, 99982193, 99982133, 99982109, 99982097, 99982079, 99982073, 99982033, 99982013, 99982007, 99981991, 99981979, 99981967, 99981961, 99981953, 99981941, 99981929, 99981911, 99981907, 99981899, 99981887, 99981863, 99981853, 99981829, 99981823, 99981803, 99981793, 99981787};

        public static int getRandomPrime_suitable_as_MOD_for_long_multipling() {
            return options[r.nextInt(options.length)];
        }

    }
}

