서로 다른 청취자의 선택

문제

음악 스트리밍 서비스에서 작은 추천 목록을 만들기 위해 일정 시간 동안의 재생 기록을 모았다. 각 기록에는 곡 식별자와 청취자 식별자가 하나씩 들어 있다. 추천 담당자는 단순한 재생 횟수보다 얼마나 다양한 사람이 곡을 들었는지를 중요하게 생각한다. 한 사람이 같은 곡을 여러 번 재생해도 그 곡의 평가에 여러 번 반영하지 않기로 했다. 각 곡의 청취자 수는 그 곡의 기록에 등장한 서로 다른 청취자 식별자의 개수이다. 예를 들어 같은 청취자가 어떤 곡을 다섯 번 재생했다면 그 곡의 청취자 수에는 1만 더한다. 반면 같은 청취자가 서로 다른 두 곡을 들었다면 두 곡의 청취자 수에 각각 1씩 반영한다. 기록의 순서는 청취자 수에 영향을 주지 않으며, 완전히 같은 기록이 연속하거나 떨어져서 여러 번 등장할 수도 있다. 곡 식별자와 청취자 식별자는 모두 영문 소문자로만 이루어진 문자열이다. 두 종류의 식별자는 별개의 영역에 속한다. 곡 식별자와 청취자 식별자의 문자열이 우연히 같더라도 특별한 의미는 없다. 식별자의 일부가 같다는 이유로 두 곡이나 두 청취자를 합치지 않으며, 문자열 전체가 같을 때만 같은 대상으로 취급한다. 추천 목록의 대표 곡은 청취자 수가 가장 많은 곡이다. 그런 곡이 여러 개라면 곡 식별자가 사전순으로 가장 앞서는 곡을 선택한다. 사전순은 왼쪽부터 다른 문자를 비교하여 알파벳 순서가 빠른 쪽을 앞에 두는 순서이며, 한 문자열이 다른 문자열의 접두사라면 짧은 문자열이 앞선다. 주어진 기록에 한 번도 나타나지 않은 곡은 후보에 포함하지 않는다. 재생 기록은 적어도 하나 주어지므로 대표 곡은 항상 존재한다. 모든 기록을 반영한 뒤 대표 곡의 식별자와 그 곡의 청취자 수를 구해야 한다.

입력

첫째 줄에 재생 기록의 개수인 정수 N이 주어진다. 1≤N≤25,000이다.
다음 N개 줄에 곡 식별자와 청취자 식별자가 공백으로 구분되어 주어진다. 각 식별자는 길이가 1 이상 6 이하이며 영문 소문자로만 이루어진다.

출력

대표 곡의 식별자와 그 곡의 서로 다른 청취자 수를 한 줄에 공백으로 구분하여 출력한다.

7
pulse ari
mist bo
pulse ari
mist ari
pulse cy
mist bo
solo cy

mist 2

4
z a
z a
z a
z a

z 1

3
aa x
a y
a z

a 2

출처: Devin.KR 자체 제작