CF981E.Addition on Segments

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 \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.

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$.

格里沙参加了一场竞赛，遇到了如下问题：

给你一个长度为 $n$ 的数组，初始时所有元素均为 $0$。数组元素的下标从 $1$ 到 $n$ 编号。你将对数组执行 $q$ 次操作。第 $i$ 次操作由三个整数 $l_i$、$r_i$ 和 $x_i$（满足 $1 \leq l_i \leq r_i \leq n$，$1 \leq x_i \leq n$）描述，其含义是：将下标在区间 $[l_i, l_i + 1, \ldots, r_i]$ 内的每个元素均加上 $x_i$。在完成所有操作后，你需要找出数组中的最大值。

格里沙很聪明，因此他很快解决了这个问题。

然而，他大脑中却出了点问题，现在他开始思考这样一个问题：“假设我们只对数组应用操作集合的一个子集（即任意选取一部分操作执行），那么数组最大值可能取哪些值？”

请帮助格里沙，找出所有满足 $1 \leq y \leq n$ 的整数 $y$，使得存在某个操作子集（可以为空），当仅执行该子集中的操作时，数组的最大值恰好等于 $y$。

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.

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 \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.

第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 10^{4}$）—— 分别表示数组的长度以及初始问题中的查询数量。

接下来的 $q$ 行每行包含一个查询。其中第 $i$ 行包含三个整数 $l_i$、$r_i$ 和 $x_i$（$1 \leq l_i \leq r_i \leq n$，$1 \leq x_i \leq n$），表示一个将 $x_i$ 加到数组中从第 $l_i$ 个元素至第 $r_i$ 个元素（含端点）所构成区间的查询。

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.

第一行输出唯一整数 $k$，表示在对数组应用给定操作的某个子集（该子集可以为空）后，数组最大值可能等于 $1$ 到 $n$（含端点）中多少个整数。

下一行按升序输出这 $k$ 个整数——即所有可能的最大值。

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)$.

考虑第一个样例。如果只考虑第一个查询的子集，则最大值为 $1$；如果只考虑第二个查询，则最大值为 $2$；如果考虑前两个查询，则最大值变为 $3$；如果只考虑第四个查询，则最大值变为 $4$；如果考虑第四个查询及其它任意额外查询，则最大值将超过 $n$，因此你不应输出该结果。

在第二个样例中，你可以仅选取第一个查询以得到 $1$；仅选取第二个查询以得到 $2$；选取全部查询以得到 $3$。

在第三个样例中，你可以得到如下最大值：

• 通过查询 $(1)$ 可达到最大值 $2$；
• 通过查询 $(2)$ 可达到最大值 $3$；
• 通过查询 $(1, 2)$ 可达到最大值 $5$；
• 通过查询 $(3)$ 可达到最大值 $6$；
• 通过查询 $(1, 3)$ 可达到最大值 $8$；
• 通过查询 $(2, 3)$ 可达到最大值 $9$。