상품 코드 모아 보기

문제

한 온라인 쇼핑몰은 여러 판매자가 등록한 상품 정보를 한 화면에 모으고 있다. 판매자들은 같은 상품 코드를 서로 다른 방식으로 적기도 한다. 어떤 판매자는 영문자를 대문자로 쓰고, 다른 판매자는 읽기 편하도록 코드 중간에 붙임표를 넣는다. 쇼핑몰은 이런 표기 차이 때문에 같은 코드가 여러 상품처럼 보이는 일을 줄이려 한다. 이번 작업에는 N개의 등록 기록이 주어진다. 각 기록에는 상품 코드 하나가 들어 있으며, 코드는 영문 대문자와 소문자, 숫자, 붙임표로만 이루어져 있다. 쇼핑몰은 각 코드에서 붙임표를 모두 지우고 영문 대문자를 소문자로 바꾼 결과를 기준 코드라고 부른다. 숫자는 바꾸지 않으며, 남아 있는 문자들의 순서도 바꾸지 않는다. 코드에는 영문자나 숫자가 적어도 하나 있으므로 기준 코드는 빈 문자열이 되지 않는다. 붙임표는 코드의 처음이나 끝에 있을 수도 있고 여러 개가 연속할 수도 있다. 위치나 개수에 관계없이 모두 지운다. 반면 숫자 0은 지우지 않는다. 따라서 기준 코드의 맨 앞에 있는 0도 그대로 남으며, 기준 코드는 수가 아닌 문자열로 취급한다. 대소문자 변경과 붙임표 제거 이외의 변환은 하지 않는다. 쇼핑몰은 기준 코드가 같은 기록들을 한 묶음으로 모은 뒤, 기록 수가 가장 많은 묶음을 첫 화면에 소개하려 한다. 완전히 같은 원래 코드가 여러 번 입력되어도 각각 별도의 등록 기록으로 센다. 기록 수가 가장 많은 묶음이 여러 개라면 기준 코드가 사전순으로 가장 작은 묶음을 선택한다. 사전순 비교에서는 숫자 0부터 9까지가 이 순서로 먼저 오고, 그 뒤에 영문 소문자 a부터 z까지가 이 순서로 온다. 앞부분이 모두 같고 한 문자열이 다른 문자열의 접두사이면 더 짧은 문자열이 먼저 온다. 등록 기록은 적어도 하나 주어지므로 선택할 묶음은 항상 존재한다. 선택한 기준 코드와 그 묶음에 속한 기록 수를 구한다.

입력

첫째 줄에 등록 기록 수인 정수 N이 주어진다. 1 ≤ N ≤ 50,000이다.
다음 N개의 줄에 상품 코드가 한 줄에 하나씩 주어진다. 각 코드의 길이는 1 이상 30 이하이며, 모든 코드 길이의 합은 200,000 이하이다.
각 코드는 영문 대문자, 영문 소문자, 숫자, 붙임표(-)로만 이루어지며 영문자나 숫자를 적어도 하나 포함한다.

출력

첫째 줄에 선택한 기준 코드를 출력한다. 둘째 줄에 해당 기준 코드를 가진 등록 기록의 개수를 출력한다.

6
AB-7
a-b7
Cd-2
CD2
ab7
x-9

ab7
3

5
B-2
b2
A-9
a9
Z

a9
2

4
0-A
0a-
A
--a--

0a
2

출처: Devin.KR 자체 제작