게임 서버의 첫 예약 충돌

문제

한 게임의 백엔드는 여러 게임 서버에서 진행할 특별 경기의 예약을 관리한다. 특별 경기가 진행되는 동안에는 해당 서버의 자원을 모두 사용하므로, 같은 서버에서 두 경기를 동시에 진행할 수 없다. 운영 도구는 여러 경로로 모인 예약을 한꺼번에 받는다. 입력에 적힌 순서는 예약 시각이나 서버 번호의 순서와 관계가 없으며, 내용이 완전히 같은 예약도 서로 다른 예약으로 취급한다. 각 예약에는 서버 번호, 시작 시각, 종료 시각이 기록되어 있다. 시작 시각이 s이고 종료 시각이 e인 예약은 s 이상 e 미만인 시각에 서버를 사용한다. 따라서 어떤 예약의 종료 시각과 다른 예약의 시작 시각이 같다면 두 예약은 충돌하지 않는다. 서로 다른 서버의 예약은 시간이 겹치더라도 충돌하지 않는다. 모든 시각은 공통된 기준으로부터 흐른 시간을 나타내는 정수이며, 날짜나 시간대로 바꾸어 해석하지 않는다. 같은 서버의 예약 두 개가 동시에 서버를 사용하는 시각이 하나라도 있으면 그 서버에 예약 충돌이 발생한다고 한다. 어떤 시각에 세 개 이상의 예약이 겹쳐도 충돌 여부를 판단하는 규칙은 같다. 이미 발생한 충돌이 계속되는 도중 다른 예약이 시작될 수도 있지만, 운영 도구가 찾으려는 것은 전체 예약에서 충돌이 처음 발생하는 시각이다. 예약을 삭제하거나 실행 순서를 조정하지 않고, 입력으로 주어진 모든 예약이 그대로 실행된다고 가정한다. 전체 서버를 통틀어 충돌이 처음 발생하는 시각과 그 시각에 충돌하는 서버 번호를 구한다. 같은 최초 시각에 여러 서버에서 충돌이 발생하면 서버 번호가 가장 작은 서버를 선택한다. 충돌하는 예약의 번호나 개수는 출력하지 않는다. 예약이 하나뿐인 서버와 예약이 없는 서버에서는 충돌이 발생하지 않으며, 어느 서버에서도 충돌하지 않으면 정해진 값인 -1을 출력한다.

입력

첫째 줄에 예약 수 N과 서버 수 S가 공백으로 주어진다. 1 ≤ N ≤ 10,000, 1 ≤ S ≤ 1,000이다.
다음 N개 줄에는 서버 번호 r, 시작 시각 s, 종료 시각 e가 공백으로 주어진다. 1 ≤ r ≤ S, 0 ≤ s < e ≤ 1,000,000,000이다.
입력의 모든 수는 정수이다.

출력

충돌이 있으면 최초 충돌 시각과 선택한 서버 번호를 공백으로 구분하여 한 줄에 출력한다. 충돌이 없으면 -1만 출력한다.

5 3
2 10 20
1 4 9
2 18 25
1 9 12
3 18 19

18 2

4 2
2 7 12
1 7 9
2 8 10
1 8 11

8 1

3 2
1 0 5
1 5 8
2 0 8

-1

출처: Devin.KR 자체 제작