헬스장

보아자르는 막 문을 연 헬스장의 주인이다. 시장 경쟁이 치열해서, 그는 사업의 모든 부분을 전문적으로 운영하고 고객에게 고급 예약 시스템을 제공하려 한다.

헬스장에는 서로 다른 운동 기구가 $k$개 있다. 각 예약은 고객이 정한 시간 구간 안에서 기구 하나를 1시간 동안 사용하겠다는 신청이다. 시스템은 같은 기구가 같은 시각에 두 예약에 배정되지 않도록, 고객이 기구를 실제로 사용하는 정확한 시각을 정한다.

보아자르는 가까운 시간에 대한 $n$개의 신청을 이미 모두 받았다. 어떤 시점에 아무도 헬스장에 없으면 조명을 끄고 에어컨을 끄고 보충제 바를 닫을 수 있다는 점을 그는 바르게 알아챘다. 비용을 줄이기 위해, 헬스장에 최소 한 명이 있는 시간의 합이 가장 작도록 운동 일정을 짜고 싶어 한다. 이 일을 도와라.

첫 줄에 정수 $n$과 $k$가 주어진다 ($1 \le n \le 10^6$, $1 \le k \le 10^9$). $n$은 예약 신청의 수이고, $k$는 헬스장 기구의 수이다. 기구는 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$를 1시간 사용하고 싶다는 뜻이다.

모든 예약을 이행할 수 있고, 같은 기구를 두 사람이 같은 시각에 쓰지 않도록 일정을 짤 수 있다면 $n+1$개의 줄을 출력한다. 첫 줄에는 헬스장에 최소 한 명이 있는 시각의 최소 개수를 쓴다. 이어지는 $n$개의 줄 중 $i$번째 줄에는 $i$번째 예약에서 기구 $p_i$를 사용하는 시각 $t_i$를 쓴다. $t_i$는 구간 $[a_i, b_i]$의 정수이다.

그렇지 않으면 NIE를 출력한다.