[AdditionalFile5290.zip](file://AdditionalFile5290.zip?type=additional_file)

#5290. 「PA 2015」Siłownia

标签: 传统 | 时间限制: 7000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2015 Runda 5 Siłownia

Bajtazar 是一家新开健身房的老板。由于市场竞争激烈，他决定在业务的所有方面都采取专业态度，并为客户提供先进的预订系统。

健身房内有 $k$ 台不同的健身设备。每次预订的流程是，客户提出在自己选定的时间段内使用某台设备一小时的请求。然后，系统会确定客户使用设备的确切时间，确保同一设备不会同时被分配给两个不同的预订。

Bajtazar 已经收到了未来一段时间内的所有 $n$ 个预订申请。他正确地注意到，如果某个时间段内没有人在健身房锻炼，就可以关掉灯光、关闭空调并锁上补充剂吧台。为了节省开支，他希望安排锻炼时间，使健身房内至少有一人锻炼的总小时数尽可能少。请帮助他完成这项任务。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $k$ $(1 \leq n \leq 1000000, 1 \leq k \leq 10^{9})$，分别表示预订申请的数量和健身房内的设备数量。设备编号为 $1$ 到 $k$ 的整数；为简化起见，小时也按从 $1$ 开始的连续整数编号。

接下来的 $n$ 行描述预订申请：第 $i$ 行包含三个整数 $a_{i}, b_{i}, p_{i}$ $(1 \leq a_{i} \leq b_{i} \leq 10^{9}, 1 \leq p_{i} \leq k)$，表示第 $i$ 个客户的预订申请，该客户希望在从小时 $a_{i}$ 到小时 $b_{i}$（包含两端）的时间段内使用设备 $p_{i}$ 一小时。

输出格式

如果可以安排锻炼时间，使得所有预订申请得到实现，并且没有设备在同一时间被两人使用，则输出 $n+1$ 行。第一行应包含一个整数，表示健身房内至少有一人锻炼的最小小时数。接下来的 $n$ 行中，第 $i$ 行应包含一个整数 $t_{i}$，范围在 $[a_{i}, b_{i}]$ 内，表示第 $i$ 个预订中设备 $p_{i}$ 在小时 $t_{i}$ 被占用。

如果无法按照上述要求安排锻炼时间，则输出 NIE。

样例 1

输入

4 2
1 3 1
1 1 1
1 3 2
3 3 2

输出

2
3
1
1
3

样例 2

输入

3 1
1 2 1
1 2 1
1 2 1

输出

NIE