페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8693
스페셜 저지

정올 체육관 10s 256MB

문제

새로 체육관을 연 정올이는 예약 시스템을 만들었다.

체육관에는 서로 다른 운동 기구가 k개 있다. 한 사람이 예약을 할 때는, 특정 기구 1대를 1시간 동안 사용하고 싶다고 말하며, 사용 가능한 시간 구간을 함께 제시한다. 예약 시스템은 실제로 각 예약이 어느 “정확한 1시간”에 배정되어 기구가 사용될지를 정해야 하며, 같은 기구가 같은 시간에 두 사람에게 동시에 배정되면 안 된다.

정올이는 가까운 미래에 대한 n개의 예약 요청을 이미 모두 받았다. 그는 어느 시간에 체육관을 아무도 이용하지 않는다면 전등과 에어컨을 끄고, 보조제 매장도 닫을 수 있다는 점에 주목했다. 그래서 그는 “적어도 한 명이라도 체육관을 이용하는 시간”의 총 개수가 최소가 되도록 예약들을 배치하고 싶다.

이 목표를 달성하도록 예약 배정을 도와주어라.


입력

  • 첫 줄에 정수 n, k가 주어진다.

    • 1 \le n \le 1{,}000{,}000

    • 1 \le k \le 10^9
      기구는 1 \sim 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번째 고객이 기구 p_i​ 를 시간 a_i​부터 b_i​까지(포함) 중 어느 1시간에 사용하고 싶다는 뜻이다.


출력

  • 모든 예약을 만족시키면서, 어떤 기구도 같은 시간에 두 예약에 배정되지 않도록 스케줄을 만드는 것이 가능하다면:

    • 총 n+1줄을 출력한다.

    • 첫 줄: 체육관을 적어도 한 명이 이용하는 시간의 최소 개수

    • 다음 n줄 중 i번째 줄: i번째 예약에 대해 선택된 시간 t_i​ 를 출력한다.

      • t_i \in [a_i, b_i]

      • 그리고 i번째 예약의 기구 p_i​는 정확히 시간 t_i​에 1시간 사용한다고 해석한다.

  • 만약 그런 스케줄을 만드는 것이 불가능하다면:

    • 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
로그인해야 코드를 작성할 수 있어요.