Grisha 参加比赛并遇到以下问题。
给定一个大小为 $$$n$$$ 的数组,最初由零组成。数组的元素从 $$$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$$$),这意味着您应该将 $$$x_i$$$ 添加到每个带有索引的元素$$$l_i,l_i + 1,\ldots,r_i$$$。完成所有操作后,您应该找到数组中的最大值。
Grisha很聪明,所以他很快就解决了问题。
然而,他的脑子里出了问题,现在他想到了以下问题:“考虑我们对数组应用了一些操作子集。数组中最大值的可能值是多少?”
帮助 Grisha,找到 $$$1$$$ 和 $$$n$$$ 之间的所有整数 $$$y$$$,这样,如果您应用操作的某个子集(可能为空),则数组中的最大值将等于 $$$y$$$。
输入
第一行包含两个整数 $$$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$$$ 个元素(包含在内)。
输出
在第一行中打印唯一的整数 $$$k$$$,表示从 $$$1$$$ 到 $$$n$$$(含)的整数个数,在应用给定操作的某些子集(可能为空)后,该整数可以等于数组中的最大值。
在下一行中打印从 $$$1$$$ 到 $$$n$$$ 的这些 $$$k$$$ 整数 - 最大值的可能值。按升序打印这些整数。
示例
输入 #1
4 3 1 3 1 2 4 2 3 4 4
输出 #1
4 1 2 3 4
输入 #2
7 2 1 5 1 3 7 2
输出 #2
3 1 2 3
输入 #3
10 3 1 1 2 1 1 3 1 1 6
输出 #3
6 2 3 5 6 8 9
注意
考虑第一个例子。如果仅考虑第一个查询的子集,则最大值等于 $$$1$$$。如果仅进行第二个查询,则最大值等于 $$$2$$$。如果您执行前两个查询,则最大值将变为 $$$3$$$。如果仅进行第四个查询,则最大值变为 $$$4$$$。如果您执行第四个查询以及更多查询,则最大值将大于 $$$n$$$,因此您不应打印它。
在第二个示例中,您可以使用第一个查询来获取 $$$1$$$。您可以仅使用第二个查询来获取$$$2$$$。您可以进行所有查询以获得$$$3$$$。
在第三个示例中,您可以获得以下最大值:
- 您可以通过使用查询来实现 $$$2$$$ 的最大值:$$$(1)$$$。
- 您可以通过使用查询来实现 $$$3$$$ 的最大值:$$$(2)$$$。
- 您可以通过使用查询来实现 $$$5$$$ 的最大值:$$$(1, 2)$$$。
- 您可以通过使用查询来实现 $$$6$$$ 的最大值:$$$(3)$$$。
- 您可以通过使用查询来实现 $$$8$$$ 的最大值:$$$(1, 3)$$$。
- 您可以通过使用查询来实现 $$$9$$$ 的最大值:$$$(2, 3)$$$。