우체국 집중 지원 시간

문제

한 우체국은 소포 분류 작업이 몰리는 시간에 지원 인력을 배치하려 한다. 운영 담당자는 D일 동안의 작업 기록을 모았다. 각 기록에는 한 작업이 시작된 날짜와 시각, 끝난 날짜와 시각이 들어 있다. 담당자는 동시에 진행 중인 작업이 K개 이상인 시간을 혼잡 시간으로 정하고, 혼잡 상태가 가장 오래 이어지는 구간에 지원 인력을 배치하려 한다. 날짜는 관찰 첫날을 1일로 하여 D일까지의 정수로 나타낸다. 시각은 24시간제 HH:MM 형식이며, 모든 작업은 분 경계에서 시작하고 끝난다. 하루는 항상 1440분이다. 작업은 시작 시각을 포함하고 종료 시각은 포함하지 않는다. 예를 들어 1일 09:10에 시작하여 1일 09:12에 끝난 작업은 09:10부터 09:11까지의 1분과 09:11부터 09:12까지의 1분 동안 진행 중이다. 종료 시각에 다른 작업이 시작하면 두 작업이 동시에 진행된 것으로 세지 않는다. 혼잡 여부는 각 1분 구간마다 판단한다. 혼잡한 1분 구간들이 시간상 바로 이어지면 하나의 연속 구간으로 본다. 자정도 연속성을 끊지 않으므로, 전날 마지막 1분과 다음 날 첫 1분이 모두 혼잡하면 같은 구간에 속한다. 기록이 완전히 같은 작업이 여러 개 있어도 각각 별개의 작업으로 센다. 관찰 범위는 1일 00:00부터 D일의 다음 날 00:00 직전까지다. 이 범위에서 가장 긴 연속 혼잡 구간의 시작 날짜, 시작 시각, 길이를 구한다. 길이는 분 단위 정수로 나타낸다. 가장 긴 구간이 여러 개라면 가장 먼저 시작하는 구간을 선택한다. 혼잡한 1분 구간이 전혀 없으면 -1만 출력한다. 작업 기록이 없어도 같은 규칙을 적용한다.

입력

첫째 줄에 관찰 일수 D, 작업 수 N, 혼잡 기준 K가 공백으로 구분되어 주어진다. D는 1 이상 100 이하, N은 0 이상 12000 이하, K는 1 이상 12001 이하의 정수다.
다음 N개 줄에는 시작 날짜 A, 시작 시각 S, 종료 날짜 B, 종료 시각 E가 공백으로 구분되어 주어진다. A는 1 이상 D 이하이고, B는 1 이상 D+1 이하인 정수다. S와 E는 정확히 HH:MM 형식이며 HH는 00 이상 23 이하, MM은 00 이상 59 이하인 두 자리 정수다.
B가 D+1이면 E는 반드시 00:00이다. 모든 작업의 시작 시점은 종료 시점보다 엄격히 이르며, 작업 전체가 관찰 범위 안에 있다. 날짜는 시각과 함께 비교한다.

출력

혼잡한 시간이 존재하면 가장 긴 연속 혼잡 구간의 시작 날짜, 시작 시각, 길이(분)를 공백으로 구분하여 한 줄에 출력한다. 시각은 앞자리 0을 포함한 HH:MM 형식으로 출력한다. 길이가 같으면 가장 먼저 시작하는 구간을 선택한다. 혼잡한 시간이 없으면 -1만 출력한다.

2 3 2
1 23:58 2 00:03
1 23:59 2 00:02
2 00:01 2 00:04

1 23:59 4

1 2 2
1 10:00 1 10:05
1 10:05 1 10:10

-1

1 2 1
1 08:00 1 08:03
1 09:00 1 09:03

1 08:00 3

출처: Devin.KR 자체 제작