{"raw_statement":[{"iden":"statement","content":"Grisha come to a contest and faced the following problem.\n\nYou 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 \\leq l_i \\leq r_i \\leq n$, $1 \\leq x_i \\leq n$) and means that you should add $x_i$ to each of the elements with indices $l_i, l_i + 1, \\ldots, r_i$. After all operations you should find the maximum in the array.\n\nGrisha is clever, so he solved the problem quickly.\n\nHowever 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?\"\n\nHelp 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$."},{"iden":"input","content":"The first line contains two integers $n$ and $q$ ($1 \\leq n, q \\leq 10^{4}$) — the length of the array and the number of queries in the initial problem.\n\nThe 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 \\leq l_i \\leq r_i \\leq n$, $1 \\leq x_i \\leq n$), denoting a query of adding $x_i$ to the segment from $l_i$\\-th to $r_i$\\-th elements of the array, inclusive."},{"iden":"output","content":"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.\n\nIn the next line print these $k$ integers from $1$ to $n$ — the possible values of the maximum. Print these integers in **increasing order**."},{"iden":"examples","content":"Input\n\n4 3\n1 3 1\n2 4 2\n3 4 4\n\nOutput\n\n4\n1 2 3 4 \n\nInput\n\n7 2\n1 5 1\n3 7 2\n\nOutput\n\n3\n1 2 3 \n\nInput\n\n10 3\n1 1 2\n1 1 3\n1 1 6\n\nOutput\n\n6\n2 3 5 6 8 9"},{"iden":"note","content":"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.\n\nIn 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$.\n\nIn the third example you can obtain the following maximums:\n\n*   You can achieve the maximim of $2$ by using queries: $(1)$.\n*   You can achieve the maximim of $3$ by using queries: $(2)$.\n*   You can achieve the maximim of $5$ by using queries: $(1, 2)$.\n*   You can achieve the maximim of $6$ by using queries: $(3)$.\n*   You can achieve the maximim of $8$ by using queries: $(1, 3)$.\n*   You can achieve the maximim of $9$ by using queries: $(2, 3)$."}],"translated_statement":[{"iden":"statement","content":"Grisha 参加了一场竞赛，遇到了以下问题：\n\n给你一个大小为 $n$ 的数组，初始时所有元素均为零。数组的元素从 $1$ 到 $n$ 编号。你对该数组执行 $q$ 次操作。第 $i$ 次操作由三个整数 $l_i$、$r_i$ 和 $x_i$（$1 lt.eq l_i lt.eq r_i lt.eq n$，$1 lt.eq x_i lt.eq n$）描述，表示将 $x_i$ 加到索引为 $l_i, l_i + 1, dots.h, r_i$ 的每个元素上。在所有操作之后，你需要找出数组中的最大值。\n\nGrisha 很聪明，他很快解决了这个问题。\n\n但不知为何，他脑海中现在产生了这样一个问题：“假设我们对数组应用了某些操作的子集，数组的最大值可能取哪些值？”\n\n请帮助 Grisha，找出所有介于 $1$ 到 $n$ 之间的整数 $y$，使得存在某个操作子集（可能为空），应用后数组的最大值恰好为 $y$。\n\n第一行包含两个整数 $n$ 和 $q$（$1 lt.eq n, q lt.eq 10^4$）——数组长度和初始问题中的操作数。\n\n接下来的 $q$ 行每行包含一个操作。第 $i$ 行包含三个整数 $l_i$、$r_i$ 和 $x_i$（$1 lt.eq l_i lt.eq r_i lt.eq n$，$1 lt.eq x_i lt.eq n$），表示将 $x_i$ 加到从第 $l_i$ 个到第 $r_i$ 个元素（包含两端）的区间上。\n\n第一行输出一个整数 $k$，表示在应用某些子集（可能为空）的操作后，可能等于数组最大值的、介于 $1$ 到 $n$（包含）之间的整数个数。\n\n第二行输出这 $k$ 个从 $1$ 到 $n$ 的整数——即可能的最大值。请按 *递增顺序* 输出这些整数。\n\n考虑第一个例子：若仅考虑第一个操作，最大值为 $1$；若仅取第二个操作，最大值为 $2$；若取前两个操作，最大值变为 $3$；若仅取第四个操作，最大值变为 $4$；若取第四个操作再加上其他操作，最大值将超过 $n$，因此不应输出。\n\n在第二个例子中，你可以取第一个操作得到 $1$，仅取第二个操作得到 $2$，取所有操作得到 $3$。\n\n在第三个例子中，你可以得到以下最大值："},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $q$（$1 lt.eq n, q lt.eq 10^4$）——数组长度和初始问题中的操作数。接下来的 $q$ 行每行包含一个操作。第 $i$ 行包含三个整数 $l_i$、$r_i$ 和 $x_i$（$1 lt.eq l_i lt.eq r_i lt.eq n$，$1 lt.eq x_i lt.eq n$），表示将 $x_i$ 加到从第 $l_i$ 个到第 $r_i$ 个元素（包含两端）的区间上。"},{"iden":"output","content":"第一行输出一个整数 $k$，表示在应用某些子集（可能为空）的操作后，可能等于数组最大值的、介于 $1$ 到 $n$（包含）之间的整数个数。第二行输出这 $k$ 个从 $1$ 到 $n$ 的整数——即可能的最大值。请按 *递增顺序* 输出这些整数。"},{"iden":"examples","content":"输入\n4 3\n1 3 1\n2 4 2\n3 4 4\n输出\n4\n1 2 3 4 \n\n输入\n7 2\n1 5 1\n3 7 2\n输出\n3\n1 2 3 \n\n输入\n10 3\n1 1 2\n1 1 3\n1 1 6\n输出\n6\n2 3 5 6 8 9 "},{"iden":"note","content":"考虑第一个例子：若仅考虑第一个操作，最大值为 $1$；若仅取第二个操作，最大值为 $2$；若取前两个操作，最大值变为 $3$；若仅取第四个操作，最大值变为 $4$；若取第四个操作再加上其他操作，最大值将超过 $n$，因此不应输出。\n\n在第二个例子中，你可以取第一个操作得到 $1$，仅取第二个操作得到 $2$，取所有操作得到 $3$。\n\n在第三个例子中，你可以得到以下最大值：\n\n你可以通过操作 $(1)$ 实现最大值 $2$。\n你可以通过操作 $(2)$ 实现最大值 $3$。\n你可以通过操作 $(1, 2)$ 实现最大值 $5$。\n你可以通过操作 $(3)$ 实现最大值 $6$。\n你可以通过操作 $(1, 3)$ 实现最大值 $8$。\n你可以通过操作 $(2, 3)$ 实现最大值 $9$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, q \\leq 10^4 $.  \nLet $ \\mathcal{O} = \\{ (l_i, r_i, x_i) \\mid i \\in \\{1, \\dots, q\\} \\} $ be the set of $ q $ operations, where each operation $ i $ adds $ x_i $ to all elements of the array at positions $ l_i, l_i+1, \\dots, r_i $.\n\nLet $ A \\subseteq \\mathcal{O} $ be an arbitrary subset of operations (including the empty set).  \nDefine the resulting array $ \\mathbf{a}_A = (a_1, a_2, \\dots, a_n) $, where for each position $ j \\in \\{1, \\dots, n\\} $:  \n$$\na_j = \\sum_{\\substack{(l_i, r_i, x_i) \\in A \\\\ l_i \\leq j \\leq r_i}} x_i\n$$\n\nLet $ M(A) = \\max_{1 \\leq j \\leq n} a_j $ be the maximum value in the array after applying subset $ A $.\n\n**Constraints**  \n1. $ 1 \\leq l_i \\leq r_i \\leq n $ for all $ i \\in \\{1, \\dots, q\\} $  \n2. $ 1 \\leq x_i \\leq n $ for all $ i \\in \\{1, \\dots, q\\} $\n\n**Objective**  \nFind the set $ Y \\subseteq \\{1, 2, \\dots, n\\} $ of all integers $ y $ such that there exists a subset $ A \\subseteq \\mathcal{O} $ with $ M(A) = y $.  \nOutput $ |Y| $ and the elements of $ Y $ in increasing order.","simple_statement":null,"has_page_source":false}