회의실 정리가 모두 끝나는 시각

문제

여러 회의실을 운영하는 시설에서는 예약마다 회의가 끝난 뒤 정리 시간을 확보한다. 운영 담당자는 예약 기록에 적힌 회의와 정리가 모두 끝나는 시각을 구하여 야간 운영 계획에 사용하려 한다. 각 기록에는 회의 시작일, 시작 시각, 회의 시간, 정리 시간이 적혀 있다. 정리는 회의가 끝나는 순간 시작하며, 정리가 끝난 시각부터 해당 예약의 작업이 모두 완료된 것으로 본다. 시설은 날짜를 기준일로부터 지난 날의 수로 관리한다. 기준일은 0일이고, 그다음 날은 1일이다. 하루는 정확히 24시간이며 한 시간은 60분이다. 시작 시각은 24시간제의 HH:MM 형식으로 기록한다. 날짜가 바뀌어도 회의와 정리는 중단되지 않는다. 예를 들어 2일 23:50에 시작하여 회의와 정리에 합계 25분이 걸리면 완료 시각은 3일 00:15다. 완료 시각이 정확히 자정이면 다음 날의 00:00으로 나타낸다. 기록에는 여러 회의실의 예약이 함께 들어 있다. 서로 다른 기록의 작업은 동시에 진행할 수 있으며, 한 기록의 정리가 다른 기록의 시작을 늦추지는 않는다. 따라서 각 기록의 완료 시각을 독립적으로 계산하면 된다. 회의실별 배정이나 예약 사이의 충돌 여부는 판단하지 않는다. 기록이 입력된 순서도 실제 시작 시각의 순서와 일치한다고 보장하지 않는다. 입력된 기록에 1번부터 N번까지 번호를 붙인다. 완료 시각이 가장 늦은 기록의 번호와 그 완료 시각을 출력한다. 가장 늦은 완료 시각을 가진 기록이 여러 개라면 번호가 가장 작은 기록을 선택한다. 입력에는 적어도 하나의 기록이 있으므로 선택할 기록은 항상 존재한다.

입력

첫째 줄에 예약 기록의 수 N이 주어진다. N은 1 이상 20,000 이하의 정수다.
다음 N개 줄에는 D S L C가 공백으로 구분되어 주어진다. D는 시작일을 나타내는 0 이상 30 이하의 정수다. S는 HH:MM 형식의 시작 시각이며 HH는 00부터 23, MM은 00부터 59까지다. L은 회의에 걸리는 분으로 1 이상 180 이하의 정수다. C는 정리에 걸리는 분으로 0 이상 60 이하의 정수다. HH와 MM은 항상 두 자리로 주어진다.

출력

완료 시각이 가장 늦은 기록의 번호, 완료일, 완료 시각을 공백으로 구분하여 한 줄에 출력한다. 완료일은 기준일로부터 지난 날의 수를 정수로 출력하고, 완료 시각은 시와 분을 각각 두 자리로 맞춘 HH:MM 형식으로 출력한다. 동점이면 번호가 가장 작은 기록을 출력한다.

3
0 23:40 30 10
1 00:05 10 5
0 22:00 60 0

1 1 00:20

4
2 09:00 60 15
1 23:30 180 60
2 10:00 30 0
0 12:00 1 0

3 2 10:30

1
30 23:00 60 0

1 31 00:00

출처: Devin.KR 자체 제작