지원 장비의 예약 경고

문제

사내 IT 지원실은 점검용 장비를 직원에게 예약제로 빌려준다. 장비마다 번호가 있으며, 같은 날 같은 장비를 두 명 이상이 동시에 사용하도록 예약되면 담당자가 일정을 조정해야 한다. 담당자는 전체 예약 목록에서 일정 충돌이 있는 장비를 찾아 경고 보고서를 만들려고 한다. 모든 예약은 같은 하루 안에 시작하고 끝난다. 각 예약에는 장비 번호, 시작 시각, 종료 시각이 기록되어 있다. 시각은 그날 0시부터 지난 분의 수로 표현한다. 예약자는 시작 시각부터 장비를 사용할 수 있고 종료 시각에는 사용을 마친다. 따라서 한 예약의 종료 시각과 다른 예약의 시작 시각이 같으면 두 예약은 충돌하지 않는다. 예를 들어 한 예약이 100분에 끝나고 다른 예약이 100분에 시작하는 것은 허용된다. 서로 다른 두 예약의 장비 번호가 같고, 두 사용 구간이 양의 길이만큼 겹치면 그 장비에는 충돌이 있다. 장비 번호가 다르면 사용 시간이 완전히 같아도 충돌이 아니다. 시작과 종료 시각이 모두 같은 예약이 여러 번 입력되면 각각 별개의 예약으로 취급하며, 같은 장비에 대한 그러한 예약들은 서로 충돌한다. 한 예약이 다른 예약의 사용 구간을 완전히 포함하는 경우도 충돌에 해당한다. 보고서에는 충돌이 있는 장비의 수와, 그중 번호가 가장 작은 장비의 번호를 기록한다. 하나의 장비에서 충돌하는 예약 쌍이 여러 개 발견되더라도 장비 수에는 한 번만 더한다. 충돌이 없는 장비는 세지 않으며, 예약이 없는 장비도 세지 않는다. 입력 순서는 예약 시각이나 장비 번호와 관계없다. 충돌이 있는 장비가 하나도 없다면 두 값 모두 0으로 기록한다. 주어진 예약 목록을 조사하여 보고서에 들어갈 두 정수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 예약 수 N이 주어진다. N은 정수이며 1 ≤ N ≤ 20,000이다.
다음 N개 줄에 장비 번호 D, 시작 시각 S, 종료 시각 E가 공백으로 구분되어 주어진다. 모두 정수이며 1 ≤ D ≤ 1,000, 0 ≤ S < E ≤ 1,440이다. 종료 시각 1,440은 다음 날 0시를 나타낸다.

출력

충돌이 있는 장비의 수와 그중 가장 작은 장비 번호를 공백으로 구분하여 출력한다. 충돌이 있는 장비가 없다면 0 0을 출력한다.

6
7 60 120
3 10 50
7 100 130
3 50 90
9 200 300
9 220 250

2 7

4
2 0 30
2 30 60
5 0 30
2 60 90

0 0

3
4 100 200
4 100 200
4 150 180

1 4

출처: Devin.KR 자체 제작