항공권 코드의 대표 표기

문제

한 여행 모임은 함께 구입한 항공권의 예약 코드를 모아 확인하고 있다. 각 참여자는 종이 항공권에 적힌 코드를 보고 문자로 입력했는데, 어떤 사람은 글자 사이의 붙임표를 그대로 입력했고 어떤 사람은 붙임표를 생략했다. 알파벳을 대문자로 적은 사람도 있고 소문자로 적은 사람도 있다. 모임에서는 이러한 표기 차이를 없앤 뒤 가장 많이 등장한 코드를 대표 코드로 정하려 한다. 입력된 코드 하나를 정리하는 방법은 다음과 같다. 먼저 코드에 들어 있는 붙임표 문자 -를 모두 지운다. 이어서 영문 소문자를 대응하는 영문 대문자로 바꾼다. 영문 대문자와 숫자는 그대로 둔다. 남은 문자들의 순서는 바꾸지 않으며, 같은 문자가 연속으로 나타나더라도 합치거나 지우지 않는다. 숫자 0도 다른 숫자와 똑같은 문자로 취급하므로 맨 앞에 있더라도 그대로 남긴다. 이 과정을 거친 문자열이 같으면 같은 코드로 취급한다. 예를 들어 q-07과 Q07은 같은 코드이고, Q7은 이들과 다른 코드이다. 붙임표가 맨 앞이나 맨 뒤에 있거나 여러 개 연속되어 있어도 정리 방법은 같다. 모든 입력 코드에는 영문자 또는 숫자가 적어도 하나 있으므로 정리 결과가 빈 문자열이 되는 경우는 없다. 같은 코드의 등장 횟수는 해당 코드로 정리되는 입력 줄의 개수이다. 같은 표기가 여러 줄에 반복되어도 매번 등장 횟수에 포함한다. 등장 횟수가 가장 큰 코드를 대표 코드로 선택한다. 그러한 코드가 여러 개라면 정리된 문자열을 사전순으로 비교하여 가장 앞선 것을 선택한다. 사전순 비교에서는 문자 순서를 0부터 9, A부터 Z의 순서로 정한다. 처음으로 다른 문자가 나오는 위치에서 앞선 문자를 가진 문자열이 먼저이며, 한 문자열이 다른 문자열의 접두사이면 짧은 문자열이 먼저이다. 대표 코드와 그 등장 횟수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 코드 개수인 정수 N이 주어진다. 1≤N≤15,000이다.
다음 N개 줄에 코드가 하나씩 주어진다. 각 코드는 길이가 1 이상 20 이하이며, 영문 대문자, 영문 소문자, 숫자, 붙임표 -로만 이루어진다. 각 코드에는 영문자 또는 숫자가 적어도 하나 있다. 공백은 포함되지 않는다.

출력

첫째 줄에 정리된 대표 코드를 출력한다. 둘째 줄에 그 코드의 등장 횟수를 출력한다.

6
b-02
A1
B02
a-1
b0-2
A-01

B02
3

4
ab
A
0-a
0A

0A
2

4
ab
A-b
A
-a-

A
2

출처: Devin.KR 자체 제작