题目背景

译自 PA 2015 R5.

题目描述

健身房里有 $k$ 个器材。

有 $n$ 个人预约了健身。第 $i$ 个人预约给定了 $l_i,r_i,p_i$，意思是要分配给他 $l_i,l_{i}+1,\cdots,r_i$ 中的一个（记为 $x$），他在第 $x$ 个小时中用器材 $p_i$ 健身。

同一时间不能有两个人用同一个健身器材。此外，老板还希望让健身房里没人的时刻尽量多，这样可以节约电费。

构造一组最优解。

输入格式

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

接下来 $n$ 行，第 $i$ 行三个正整数 $l_i,r_i,p_i$。

输出格式

如果无解，输出一行一个 $\texttt{NIE}$。

否则输出 $(n+1)$ 行：第一行一个整数，表示在最优策略下，有多少个时刻健身房至少有一个人。接下来 $n$ 行，第 $i$ 行的整数表示第 $i$ 个人分配的 $x$。

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

2
3
1
1
3

3 1
1 2 1
1 2 1
1 2 1

NIE

提示

• $1\le n\le 10^6$；
• $1\le k\le 10^9$；
• $1\le l_i\le r_i\le 10^9$；
• $1\le p_i\le k$。