Bajtazar 拥有一家新开的健身房。由于市场竞争激烈，他决定以专业的方式处理业务的各个方面，并为客户提供先进的预订系统。

健身房内有 $k$ 种不同的健身器材。每项预订的流程是：客户在自己选定的时间段内，申请使用某台器材一小时。系统随后会确定客户使用器材的具体时间，以确保没有任何器材在同一时间被分配给两项不同的预订。

Bajtazar 已经收到了近期所有的 $n$ 个预订申请。他敏锐地发现，如果某个时刻没有人使用健身房，就可以关灯、关闭空调并关闭补给品吧台。为了节省开支，他希望安排锻炼时间，使得健身房内至少有一人锻炼的总小时数尽可能少。请帮助他完成这项任务。

输入格式

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

接下来的 $n$ 行描述了预订申请：第 $i$ 行包含三个整数 $a_i, b_i$ 和 $p_i$ ($1 \le a_i \le b_i \le 10^9$, $1 \le p_i \le k$)，表示第 $i$ 位客户希望在时间段 $[a_i, b_i]$（含边界）内使用器材 $p_i$ 一小时。

输出格式

如果能够安排锻炼，使得所有预订都得到满足，且没有任何器材在同一时间被两人使用，则输出 $n+1$ 行。第一行应包含健身房内至少有一人锻炼的最小总小时数。接下来的 $n$ 行中，第 $i$ 行应包含一个区间 $[a_i, b_i]$ 内的整数 $t_i$，表示第 $i$ 项预订中器材 $p_i$ 在第 $t_i$ 小时被占用。

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

样例

输入 1

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

输出 1

2
3
1
1
3

输入 2

3 1
1 2 1
1 2 1
1 2 1

输出 2

NIE