최고의 동접 구간을 찾아라!

NYPC 2018 · 예선

게임 분석가 승민이는 넥슨의 게임 메이플스토리가 얼마나 인기가 높은지 알고 싶어졌다. 게임의 인기는 접속한 유저 수로 알 수 있고, 특히 동시에 몇 명의 유저가 접속해 있는지를 아는 것은 게임의 인기 뿐 아니라, 게임의 관리자 입장에서도 얼마나 많은 자원을 투자해야 하는지 중요한 자료가 된다. 따라서 승민이는 가장 많은 유저들이 동시에 접속한 구간을 손쉽게 찾아내고 싶다.

넥슨은 승민이에게 유저들의 로그인 시간과 로그아웃 시간이 저장된 로그 파일을 제공했다. 여러분은 승민이를 도와서, 이 로그 파일을 이용하여 가장 많은 유저들이 동시에 접속한 구간을 찾아내는 프로그램을 작성하자.

입력 형식

첫째 줄에 로그의 수 NN (1N3000001 \le N \le 300\,000)가 입력된다.

다음 NN 줄에 유저 하나가 로그인한 시간과 로그아웃한 시간이 공백으로 구별되어 주어진다.

출력 형식

가장 많은 유저가 동시에 접속한 기간을 찾아서, 먼저 이 기간에 로그인한 유저의 수를 출력한다. 다음, 이 기간의 시작 시간과 종료 시간을 각각 2424시간의 형태로 hh:mm, 즉 시:분의 형태로 출력한다. 만약 이러한 기간이 둘 이상 있다면, 가장 먼저 시작한 기간을 출력한다.

예제 1

입력

5 09:00 11:20 11:00 13:50 12:00 15:00 13:00 16:20 15:50 18:45

출력

3 13:00 13:50

예제 2

입력

2 09:00 09:59 10:00 11:00

출력

1 09:00 09:59

예제 3

입력

3 01:00 08:00 02:00 03:00 03:00 05:00

출력

2 02:00 05:00

예제 33번의 풀이를 보다 자세히 설명하면, 다음과 같다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 10

N2N \le 2

종류 2: 40

N5000N \le 5\,000

종류 3: 50

문제의 원래 제한조건 이외의 추가된 제한이 없음.

해설