은행 창구의 가장 바쁜 순간

문제

한 은행은 여러 창구에서 처리한 상담 기록을 모아 창구 운영 보고서를 작성한다. 보고서에는 조사 기간 중 동시에 진행 중이던 상담 수의 최댓값과, 그 수가 처음 나타난 시각을 넣는다. 기록에는 창구 번호나 고객 이름 없이 상담한 날짜, 시작 시각, 종료 시각만 남아 있다. 담당자는 이 기록만으로 필요한 값을 구하려고 한다. 조사 기간은 연속된 D일이며, 첫날을 1일, 마지막 날을 D일로 표시한다. 모든 날의 영업시간은 09:00부터 17:00까지다. 모든 상담은 한 날짜 안에서 시작하고 끝나며, 시작 시각은 종료 시각보다 반드시 이르다. 기록의 시각은 모두 분 단위이고 초는 사용하지 않는다. 날짜 번호는 조사 기간 안의 순서이므로 월의 길이, 요일, 공휴일은 고려하지 않는다. 상담은 시작 시각부터 진행 중인 것으로 세고, 종료 시각부터는 진행 중인 것으로 세지 않는다. 예를 들어 어떤 상담이 10:20에 끝나고 다른 상담이 10:20에 시작하면, 그 시각에는 새로 시작한 상담만 센다. 같은 날짜에 시작 시각과 종료 시각이 모두 같은 기록이 여러 개 있더라도 각각 별개의 상담이다. 서로 다른 창구의 상담이므로 기록끼리 시간이 겹칠 수도 있다. 입력 기록은 날짜나 시각 순서로 정렬되어 있지 않다. 동시에 진행 중인 상담 수가 최대인 순간이 여러 번 있으면 날짜가 가장 이른 순간을 고르고, 그 날짜 안에서는 시각이 가장 이른 순간을 고른다. 상담 기록이 하나도 없으면 최댓값은 0이며, 그 값이 처음 나타난 날짜와 시각은 출력하지 않는다. 주어진 기록을 이용하여 보고서에 들어갈 값을 구한다.

입력

첫째 줄에 조사 기간의 일수 D와 상담 기록 수 N이 공백으로 구분되어 주어진다. D와 N은 정수이며 1 ≤ D ≤ 365, 0 ≤ N ≤ 20,000이다.
다음 N개 줄에는 날짜 번호 d, 시작 시각 s, 종료 시각 e가 공백으로 구분되어 주어진다. d는 1 ≤ d ≤ D인 정수다. s와 e는 각각 두 자리 시와 두 자리 분으로 이루어진 HH:MM 형식이며, 09:00 ≤ s < e ≤ 17:00이다. 분은 00부터 59까지의 정수다. 각 기록은 정확히 하나의 상담을 나타내며, 동일한 기록이 여러 번 주어질 수 있다.

출력

N이 1 이상이면 동시에 진행 중인 상담 수의 최댓값, 그 최댓값이 처음 나타난 날짜 번호, 해당 시각을 공백으로 구분하여 한 줄에 출력한다. 시각은 HH:MM 형식으로 출력한다. N이 0이면 0 -1을 한 줄에 출력한다.

3 5
2 09:00 10:00
1 10:00 11:00
1 09:30 10:30
1 10:30 12:00
2 09:15 09:45

2 1 10:00

2 4
2 09:00 09:01
1 16:59 17:00
1 09:00 09:30
1 09:30 10:00

1 1 09:00

365 0

0 -1

출처: Devin.KR 자체 제작