题目描述

你在研究蚂蚁🐜的行为模式。

通过分析观察到的数据，你预测到，在接下来的 $m$ 天中，蚁后🐜🐜会发布两种类型的任务共 $n$ 个，第 $i$ 个任务的类型为 $c_i\in \{0,1\}$，会在第 $s_i$ 天发布；而如果在第 $t_i$ 天之前（包括第 $t_i$ 天）这个任务还没有被完成，蚁后🐜🐜就会取消这个任务。

蚂蚁🐜的行为模式比较单一，具体来说，在每一天，蚂蚁🐜首先会选择一个类型 $p\in \{0,1\}$，然后找到类型为 $p$ 的所有已经被发布，且仍未被取消，且目前尚未被完成的任务中，截止日期最靠前，在此基础上编号最小的一个任务（即，设当前是第 $k$ 天，那么蚂蚁🐜会选取 $c_i=p,s_i\le k\le t_i$ 且 $t_i$ 最小的任务 $i$ 中，$i$ 最小的一个），在这一天完成这个任务。如果类型为 $p$ 的任务都已经被完成或者被取消，或者仍未被发布，那么蚂蚁🐜在这一天就会选择休息。

你的研究已经取得了一些成果，具体来说，你可以在接下来的 $m$ 天中控制蚂蚁🐜在每一天选择的任务类型 $p$ 具体是 $0$ 还是 $1$。为了获得一些更有价值的数据，你希望你选择的这个方案能够让蚂蚁🐜完成的任务数量最小化。

现在请你设计一种方案，使得蚂蚁🐜完成的任务数量最小，并求出这个最小值是多少。

输入格式

从文件 designant.in 中读入。

第一行两个正整数 $n,m$。

接下来 $n$ 行，每行三个整数 $s_i,t_i,c_i$。

输出格式

输出到文件 designant.out 中。

第一行一个非负整数表示蚂蚁🐜完成的任务数量的最小值。

第二行一个长为 $n$ 的 01 串，以空格分隔，表示你为蚂蚁🐜每一天选择的类型。

样例 $1$ 输入

6 6
4 6 1
1 2 0
2 6 1
1 5 0
2 3 0
4 5 1

样例 $1$ 输出

2
1 1 1 0 0 0

样例 $1$ 解释

按照你选择的方案，蚂蚁🐜每一天的行为分别是：

• 第一天，类型为 $1$ 的任务都没有被发布，因此无事可做。
• 第二天，发布了类型为 $1$ 的任务 $3$，因此在这一天做完任务 $3$。
• 第三天，类型为 $1$ 的任务要么已经被做完，要么都没有被发布，因此这一天无事可做。
• 第四天，这天需要做类型为 $0$ 的任务，此时只有任务 $4$ 仍未结束，因此这一天做完任务 $4$。
• 第五、六天，类型为 $0$ 的任务要么被做完了，要么都结束了，因此这两天都无事可做。

这样，蚂蚁🐜一共只完成了两个任务，是可能的最小值。

样例 $2$ 输入

9 10
1 1 0
2 7 1
1 1 1
4 4 0
10 10 0
3 7 0
6 10 1
4 9 1
7 8 0

样例 $2$ 输出

4
0 0 1 1 1 1 1 1 0 1

样例 $2$ 解释

按照这个方案，蚂蚁🐜分别在第 $1,3,4,6$ 天完成了第 $1,2,8,7$ 号任务。

样例 $3,4,5$

见下发文件：下载链接

同时我们还在下发文件中提供了 checker.cpp。最终测试使用的 checker.cpp 与该文件相同。

注意大样例的 ans 文件中只提供了答案，没有给出具体的方案；checker.cpp 会检测你的方案是否合法。

checker 使用方法如下：

下发文件中有 checker.cpp 和 testlib.h。将两个文件放在同一目录下后，即可编译 checker.cpp 得到可执行文件 checker。

如果你在 Linux 系统下，使用命令：

./checker <input-file> <output-file> <answer-file>

如果你在 Windows 系统下，使用命令：

checker <input-file> <output-file> <answer-file>

即可检验你的输出正确性。

其中 <input-file> <output-file> <answer-file> 分别对应输入文件，输出文件和答案文件。

测试点约束

对于所有数据，$1\le n,m\le 5\times 10^4,1\le s_i\le t_i\le m,c_i\in \{0,1\}$。

子任务编号	$n,m\le$	特殊性质	分值
Subtask 1	$15$	无	$12$
Subtask 2	$50$	无	$14$
Subtask 3	$400$	无	$22$
Subtask 4	$3000$	无	$14$
Subtask 5	$5\times 10^4$	$s_i=1$	$10$
Subtask 6	$5\times 10^4$	无	$28$

此外，对于每个测试点，如果你输出的答案正确，但是构造的方案错误，则你可以获得该测试点 $50\%$ 的分数；一个子任务的分数为这个子任务内所有测试点的分数的最小值。

注意，即使你不会构造方案，也请在第二行输出一个长为 $m$ 的 01 串，以空格分隔，否则该测试点将被判为 $0$ 分。