세 관문 기록 정리

문제

마라톤 대회 코스에는 출발 관문, 중간 관문, 도착 관문이 있으며 각각 1번, 2번, 3번으로 표시되어 있다. 각 관문의 장치는 참가자의 배번호와 관문 번호, 감지 시각을 기록한다. 운영팀은 대회가 끝난 뒤 여러 장치의 기록을 하나로 모았지만, 모인 기록은 시각순으로 정렬되어 있지 않다. 장치는 한 참가자를 같은 관문에서 여러 번 감지할 수 있다. 따라서 같은 배번호와 같은 관문 번호를 가진 기록이 여러 개 있을 수 있으며, 세 값이 모두 같은 기록도 반복될 수 있다. 운영팀은 각 참가자의 각 관문에 대해 감지 시각이 가장 작은 기록 하나만 대표 기록으로 사용하기로 했다. 다른 기록을 골라 더 유리한 결과를 만드는 것은 허용하지 않는다. 어떤 참가자의 1번, 2번, 3번 관문 대표 시각을 각각 S, M, F라고 하자. 세 관문의 대표 기록이 모두 존재하고 S < M < F를 만족할 때만 그 참가자를 유효 완주자로 인정한다. 어느 관문의 기록이 없거나, 대표 시각의 순서가 이 조건을 만족하지 않으면 유효 완주자가 아니다. 두 관문의 대표 시각이 같은 경우도 인정하지 않는다. 유효 완주자의 소요 시간은 F에서 S를 뺀 값이다. 중간 관문의 대표 시각은 통과 순서를 확인하는 데 사용되며, 소요 시간을 계산할 때 따로 더하거나 빼지 않는다. 모든 시각은 대회의 기준 시점부터 지난 초를 나타내는 정수이다. 운영팀은 유효 완주자 중 소요 시간이 가장 짧은 참가자 한 명을 선정하려 한다. 소요 시간이 같은 참가자가 여러 명이면 배번호가 가장 작은 참가자를 선정한다. 주어진 모든 기록을 위 규칙대로 정리한 뒤, 선정된 참가자의 배번호와 소요 시간을 구하는 프로그램을 작성한다. 유효 완주자가 한 명도 없을 수도 있다.

입력

첫째 줄에 기록의 수를 나타내는 정수 N이 주어진다.
1 ≤ N ≤ 20,000
다음 N개의 줄에 정수 B, G, T가 공백으로 구분되어 주어진다. 각각 배번호, 관문 번호, 감지 시각이다.
1 ≤ B ≤ 10,000
1 ≤ G ≤ 3
0 ≤ T ≤ 1,000,000
입력에 등장하지 않는 배번호는 선정 대상이 아니다. 기록의 입력 순서는 감지 시각과 무관하며, 같은 기록이 여러 번 주어질 수 있다.

출력

유효 완주자가 있으면 선정된 참가자의 배번호와 소요 시간을 공백으로 구분하여 한 줄에 출력한다. 유효 완주자가 없으면 -1만 출력한다.

10
42 3 90
7 2 35
42 1 10
7 1 20
42 2 50
7 3 70
9 3 65
9 1 15
9 2 40
42 1 12

7 50

5
3 1 10
3 2 10
3 3 20
8 1 2
8 3 9

-1

4
5 1 10
5 2 20
5 3 30
5 3 5

-1

출처: Devin.KR 자체 제작