급식 메뉴 표기의 대표 이름

문제

한 학교는 학생들이 급식 메뉴를 검색할 때 자주 사용하는 이름을 조사하고 있다. 조사 자료에는 학생이 입력한 메뉴 표기가 한 줄에 하나씩 저장되어 있다. 메뉴 표기는 실제 음식 이름 대신 영문자로 만든 짧은 식별 이름을 사용한다. 학생마다 대문자와 소문자를 다르게 쓰거나 읽기 편하도록 붙임표를 넣어서, 같은 메뉴가 여러 형태로 기록되어 있다. 자료를 정리하기 위해 각 표기에 다음 두 처리를 모두 적용한 결과를 표준 이름으로 정한다. 먼저 붙임표인 문자 '-'를 모두 없애고, 영문 대문자를 대응하는 영문 소문자로 바꾼다. 이 두 처리 외에는 어떤 문자도 추가하거나 삭제하거나 순서를 바꾸지 않는다. 예를 들어 'Ri-CE'와 'r-ice'의 표준 이름은 모두 'rice'다. 입력 표기에는 영문자가 적어도 하나 있으므로 표준 이름이 빈 문자열이 되는 경우는 없다. 표준 이름이 같은 기록들은 같은 메뉴를 가리킨다. 학교는 전체 기록에서 가장 많이 등장한 메뉴 하나를 대표 메뉴로 정하려 한다. 등장 횟수는 서로 다른 원래 표기의 수가 아니라 기록의 개수로 센다. 따라서 완전히 같은 표기가 여러 줄 입력되어도 각 줄을 한 번씩 세어야 한다. 반대로 원래 표기가 서로 달라도 표준 이름이 같으면 그 횟수를 합친다. 등장 횟수가 가장 많은 표준 이름이 여럿이면 사전순으로 가장 앞선 이름을 선택한다. 사전순은 영문 소문자 'a'부터 'z'까지의 순서를 사용한다. 두 이름을 앞에서부터 비교해 처음 다른 문자가 더 앞선 쪽이 먼저이며, 한 이름이 다른 이름의 접두사라면 더 짧은 이름이 먼저다. 입력 순서는 선택에 영향을 주지 않는다. 선택한 대표 메뉴의 표준 이름과 등장 횟수를 출력하는 프로그램을 작성한다.

입력

첫째 줄에 기록 수인 정수 N이 주어진다. 1 ≤ N ≤ 20,000이다.
다음 N개 줄에 메뉴 표기가 하나씩 주어진다. 각 표기의 길이는 1 이상 12 이하이고, 영문 대문자, 영문 소문자, 붙임표 '-'로만 이루어진다. 각 표기에는 영문자가 적어도 하나 포함된다. 공백은 포함되지 않는다.

출력

대표 메뉴의 표준 이름과 등장 횟수를 공백으로 구분하여 한 줄에 출력한다. 입력 기록이 적어도 하나이므로 대표 메뉴는 항상 존재한다.

6
Ri-CE
r-ice
SOUP
so-up
rice
Bean

rice 3

4
B-ean
APPLE
bean
ap-ple

apple 2

3
a-b
A
-a-

a 2

출처: Devin.KR 자체 제작