지원 요청의 대표 코드

문제

한 회사의 사내 IT 지원팀은 직원이 보낸 요청에 짧은 분류 코드를 붙여 저장한다. 예를 들어 같은 장비에 관한 요청이라도 발생한 문제가 다르면 서로 다른 코드가 붙을 수 있다. 반대로 여러 직원이 보낸 요청에 같은 코드가 붙을 수도 있다. 이번 작업에서는 요청의 내용이나 작성자를 사용하지 않고, 저장된 코드만으로 하루의 요청 현황을 요약한다. 하루 동안 접수된 요청 N개의 코드가 접수 순서대로 주어진다. 코드 하나는 영어 소문자로만 이루어진 길이 1 이상 3 이하의 문자열이다. 두 코드가 같다는 것은 길이가 같고 모든 위치의 문자가 같다는 뜻이다. 한 코드가 다른 코드의 앞부분에 포함되어 있더라도 두 문자열 전체가 같지 않으면 서로 다른 코드로 취급한다. 공백이나 대문자가 코드에 포함되는 경우는 없다. 지원팀은 요약 화면에 표시할 대표 코드 하나를 정한다. 대표 코드는 전체 요청에서 등장 횟수가 가장 많은 코드다. 같은 요청이 여러 번 저장되어 있더라도 입력의 각 줄을 별개의 요청으로 세므로, 같은 코드가 적힌 모든 줄이 등장 횟수에 포함된다. 등장 횟수가 가장 많은 코드가 둘 이상이면 그중 사전순으로 가장 앞서는 코드를 대표 코드로 선택한다. 접수된 시각이나 처음 등장한 위치는 동점 처리에 사용하지 않는다. 사전순은 영어 알파벳 순서를 따른다. 두 문자열을 왼쪽부터 비교하여 처음으로 다른 문자가 나타난 위치에서 더 앞선 알파벳을 가진 문자열이 먼저 온다. 한 문자열이 다른 문자열의 앞부분과 완전히 같으면 짧은 문자열이 먼저 온다. 대표 코드와 그 코드의 등장 횟수, 그리고 하루 동안 등장한 서로 다른 코드의 수를 구한다. 서로 다른 코드의 수를 셀 때는 같은 코드가 몇 번 등장했는지와 관계없이 한 종류로 센다. 요청은 적어도 하나 주어지므로 대표 코드는 항상 존재한다.

입력

첫째 줄에 요청 수를 나타내는 정수 N이 주어진다. 1≤N≤100,000이다.
다음 N개 줄에 요청 코드가 하나씩 주어진다. 각 코드는 영어 소문자로만 이루어지며 길이는 1 이상 3 이하이다.

출력

첫째 줄에 대표 코드와 그 코드의 등장 횟수를 공백으로 구분하여 출력한다. 둘째 줄에 서로 다른 코드의 수를 정수로 출력한다.

6
a
b
a
c
b
b

b 3
3

4
z
aa
z
aa

aa 2
2

1
it

it 1
1

출처: Devin.KR 자체 제작