항공권 변경 창구의 가장 바쁜 분

문제

한 항공권 판매소는 예약 변경 요청을 처리하는 동안 요청마다 작업 기록 하나를 남긴다. 각 기록에는 작업을 시작한 날짜와 시각, 작업을 끝낸 날짜와 시각이 저장된다. 담당자는 이 기록을 이용하여 동시에 처리 중이었던 요청이 가장 많았던 때를 찾으려 한다. 분석 기간은 기준일인 0일의 00:00부터 99일의 23:59까지이다. 날짜는 기준일에서 지난 날의 수를 나타내는 정수이다. 달이나 연도는 따로 사용하지 않으며, 모든 날은 정확히 24시간이고 한 시간은 정확히 60분이다. 모든 시각은 같은 시간대를 사용한다. 기록의 시각은 분 단위로만 주어지며 초는 고려하지 않는다. 작업 하나는 시작 시각부터 처리 중인 것으로 계산하고, 종료 시각부터는 처리 중인 것으로 계산하지 않는다. 예를 들어 2일 23:58에 시작하여 3일 00:01에 끝난 작업은 2일 23:58, 2일 23:59, 3일 00:00의 세 분에 포함된다. 어떤 작업이 끝나는 시각에 다른 작업이 시작한다면, 그 시각에는 새로 시작한 작업만 포함된다. 기록은 작업마다 하나씩 주어진다. 시작과 종료가 모두 같은 두 기록이 있더라도 서로 다른 요청의 작업이므로 각각 하나씩 센다. 작업은 날짜가 바뀌어도 중단되지 않으며, 주어진 시작 시각과 종료 시각 사이의 모든 분에서 계속 처리 중이다. 기록이 입력되는 순서에는 아무 의미가 없다. 분석 기간의 각 분에 대하여 처리 중인 작업 개수를 구했을 때, 그 최댓값과 최댓값이 처음 나타난 날짜 및 시각을 출력한다. 같은 최댓값을 갖는 분이 여러 개라면 시간상 가장 이른 분을 선택한다. 기록이 하나도 없으면 최댓값은 0이고 선택하는 시각은 0일 00:00이다.

입력

첫째 줄에 작업 기록 개수인 정수 N이 주어진다. 0≤N≤15,000이다.
다음 N개 줄에는 시작 날짜, 시작 시각, 종료 날짜, 종료 시각이 공백으로 주어진다. 날짜는 0 이상 99 이하의 정수이고, 시각은 HH:MM 형식이다. HH는 두 자리의 00부터 23까지, MM은 두 자리의 00부터 59까지이다.
각 기록의 시작 시각은 종료 시각보다 반드시 이르다. 모든 시작과 종료 시각은 분석 기간 안에 있다.

출력

동시에 처리 중인 작업 개수의 최댓값, 선택한 날짜, 선택한 시각을 공백으로 구분하여 한 줄에 출력한다. 날짜는 불필요한 앞자리 0 없이 출력하고, 시각은 HH:MM 형식으로 출력한다.

3
0 23:58 1 00:02
1 00:00 1 00:03
1 00:02 1 00:04

2 1 00:00

0

0 0 00:00

2
4 09:00 4 09:01
4 09:01 4 09:02

1 4 09:00

출처: Devin.KR 자체 제작