Moamen 正在绘制一个由 $$$n$$$ 行和 $$$10^9$$$ 列组成的网格,其中仅包含数字 $$$0$$$ 和 $$$1$$$。埃扎特注意到了莫阿曼正在画的东西,并对一个人需要删除多少行才能使网格变得漂亮产生了兴趣。
网格是漂亮的当且仅当每连续两行中至少有一列包含 $$$1$$$ 。
Ezzat 将为您提供 $$$n$$$ 行数以及包含数字 $$$1$$$ 的网格 $$$m$$$ 段数。每个段都用三个整数 $$$i$$$、$$$l$$$ 和 $$$r$$$ 表示,其中 $$$i$$$ 表示行号,$$$l$$$ 和 $$$r$$$ 表示该行中段的第一列和最后一列。
例如,如果 $$$n = 3$$$、$$$m = 6$$$,并且段为 $$$(1,1,1)$$$、$$$(1,7,8)$$$、$$$(2,7,7)$$$、$$$(2,15,15)$$$、$$$(3,1,1)$$$、 $$$(3,15,15)$$$,则网格为:
你的任务是告诉 Ezzat 为使网格美观而应删除的最少行数。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 3\cdot10^5$$$)。
接下来的 $$$m$$$ 行包含三个整数 $$$i$$$、$$$l$$$ 和 $$$r$$$ ($$$1 \le i \le n$$$、$$$1 \le l \le r \le 10^9$$$)。这些 $$$m$$$ 行中的每一行都表示行号 $$$i$$$ 在从 $$$l$$$ 到 $$$r$$$(含)的列中包含数字 $$$1$$$。
请注意,这些段可能会重叠。
输出
在第一行中,打印一个整数 $$$k$$$ — 应删除的最小行数。
在第二行中打印 $$$k$$$ 不同的整数 $$$r_1, r_2, \ldots, r_k$$$,表示应以任意顺序删除的行 ($$$1 \le r_i \le n$$$)。
如果有多个答案,请打印其中一个。
示例
输入 #1
3 6 1 1 1 1 7 8 2 7 7 2 15 15 3 1 1 3 15 15
输出 #1
0
输入 #2
5 4 1 2 3 2 4 6 3 3 5 5 1 1
输出 #2
3 2 4 5
注意
在第一个测试用例中,网格是问题陈述中解释的网格。网格具有以下属性:
1. $$$1$$$-st 行和 $$$2$$$-nd 行在 $$$7$$$ 列中具有共同的 $$$1$$$。
2. $$$2$$$-nd 行和 $$$3$$$-rd 行在 $$$15$$$ 列中具有共同的 $$$1$$$。
在第二个测试用例中,给定的网格如下: