늘여 쓴 곡 검색어

문제

음악 스트리밍 서비스에는 곡을 찾을 때 사용할 짧은 검색 별칭이 등록되어 있다. 운영자는 이용자들이 같은 글자를 길게 늘여 입력하는 현상을 살펴보기 위해 검색어 기록을 모았다. 이 조사에서는 실제 곡 제목이나 검색 결과를 사용하지 않고, 입력된 검색어를 정해진 규칙으로 정리한 문자열만 비교한다. 검색어는 영문 소문자로만 이루어진다. 검색어를 왼쪽부터 읽으면서 같은 글자가 연속으로 나타나는 각 구간을 글자 하나로 줄이면 그 검색어의 대표 문자열이 된다. 길이가 1인 구간도 그대로 글자 하나를 남긴다. 예를 들어 aaabbba는 a 세 개, b 세 개, a 한 개의 구간으로 나뉘므로 대표 문자열이 aba다. 앞에서 나온 글자라도 다른 글자를 사이에 두고 다시 나타났다면 별개의 구간이다. 따라서 aba를 ab로 줄이지 않는다. 각 검색 기록은 자신의 대표 문자열에 한 표를 더한다. 원래 검색어의 길이나 같은 글자가 반복된 횟수는 표의 크기에 영향을 주지 않는다. 완전히 같은 검색어가 여러 번 기록되었더라도 각 기록은 독립적으로 한 표를 더한다. 운영자는 가장 많은 표를 받은 대표 문자열 하나를 이번 조사에서 주목할 별칭으로 정한다. 가장 많은 표를 받은 대표 문자열이 여러 개라면 사전 순으로 가장 앞서는 문자열을 선택한다. 사전 순은 왼쪽부터 처음으로 다른 글자를 비교하여 알파벳 순서가 앞선 쪽을 먼저 두는 순서다. 한 문자열이 다른 문자열의 접두사이면 짧은 문자열이 먼저 온다. 검색 기록은 적어도 하나이므로 선택할 대표 문자열은 항상 존재한다. 선택된 대표 문자열과 그 문자열이 받은 표의 수를 구하는 프로그램을 작성하라.

입력

첫째 줄에 검색 기록 수 N이 주어진다. N은 1 이상 10,000 이하의 정수다. 다음 N개 줄에는 검색어가 하나씩 주어진다. 각 검색어는 영문 소문자로만 이루어지며 길이는 1 이상 100 이하이다. 모든 검색어 길이의 합은 100,000 이하이다.

출력

선택된 대표 문자열과 그 문자열이 받은 표의 수를 한 줄에 공백으로 구분하여 출력한다.

5
aaabbba
abbaa
cccc
cc
aba

aba 3

4
zzzza
bbbaa
zaaaa
ba

ba 2

1
aaaaaa

a 1

출처: Devin.KR 자체 제작