도서관 코드 표기 통합

문제

한 도서관은 여러 열람실에서 모은 책 운반 상자의 코드 기록을 하나로 합치고 있다. 각 기록에는 상자 코드 하나가 적혀 있다. 직원마다 코드를 입력하는 습관이 달라 같은 코드에 대문자와 소문자가 섞이기도 하고, 읽기 편하도록 붙인 하이픈의 위치가 달라지기도 한다. 도서관은 이런 표기 차이를 없앤 뒤 가장 자주 기록된 코드를 대표 코드로 정하려 한다. 코드를 통합하는 규칙은 다음과 같다. 먼저 원래 코드에 있는 하이픈 문자 -를 모두 지운다. 이어서 남은 영문 대문자를 대응하는 영문 소문자로 바꾼다. 영문 소문자는 그대로 둔다. 이 과정을 마친 문자열을 해당 기록의 표준 코드라고 부른다. 하이픈의 개수와 위치는 표준 코드에 영향을 주지 않지만, 영문자의 순서는 바꿀 수 없다. 각 원래 코드에는 영문자가 적어도 하나 있으므로 표준 코드가 빈 문자열이 되는 일은 없다. 예를 들어 원래 코드가 Q-r이라면 표준 코드는 qr이다. 원래 코드가 qR이어도 같은 표준 코드를 얻는다. 하지만 rq는 영문자의 순서가 다르므로 별개의 표준 코드다. 완전히 같은 원래 코드가 여러 번 입력되거나 서로 다른 원래 코드가 같은 표준 코드로 바뀌면, 해당 기록들을 모두 그 표준 코드의 등장 횟수에 더한다. 대표 코드는 등장 횟수가 가장 많은 표준 코드다. 가장 많은 횟수를 가진 표준 코드가 여러 개라면 사전순으로 가장 앞선 것을 선택한다. 사전순 비교에서는 왼쪽부터 처음으로 다른 영문자가 나오는 위치에서 알파벳 순서가 앞선 문자를 가진 문자열이 앞선다. 한 문자열이 다른 문자열의 접두사이면 더 짧은 문자열이 앞선다. 적어도 하나의 기록이 주어지므로 대표 코드는 항상 존재한다. 대표 코드와 그 등장 횟수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 기록 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 100,000이다.
다음 N개 줄에 원래 코드가 한 줄에 하나씩 주어진다. 각 코드는 영문 대문자, 영문 소문자, 하이픈(-)으로만 이루어진다. 각 코드의 길이는 1 이상 12 이하이며, 영문자를 적어도 하나 포함한다. 모든 원래 코드의 길이의 합은 250,000 이하이다. 코드에는 공백이 없다.

출력

첫째 줄에 대표 표준 코드를 출력한다. 둘째 줄에 그 표준 코드의 등장 횟수를 정수로 출력한다. 최다 등장 횟수가 같으면 사전순으로 가장 앞선 표준 코드를 출력한다.

7
Q-r
qR
M--n
mn
QR
mN
Z

mn
3

5
A-b
AB
A
-a-
b

a
2

1
--X-y--

xy
1

출처: Devin.KR 자체 제작