예약 코드의 겹치는 앞부분

문제

한 병원은 예약을 등록할 때마다 알파벳 대문자로 이루어진 예약 코드를 기록한다. 안내 직원은 전화로 코드를 확인할 때 앞부분부터 한 글자씩 듣는다. 서로 다른 예약 기록의 코드가 같은 문자들로 시작하면, 그 부분까지만 듣고서는 어느 기록인지 구별하기 어렵다. 병원은 안내 절차를 점검하기 위해 여러 예약 기록 사이에서 얼마나 긴 앞부분이 겹치는지 조사하려고 한다. 문자열의 접두사는 문자열의 맨 앞에서 시작하여 문자를 연속해서 몇 개 선택한 문자열이다. 이 문제에서는 한 글자 이상을 선택한 경우만 접두사로 인정한다. 문자열 전체를 선택한 것도 접두사에 포함한다. 문자열의 중간에서 시작한 부분이나, 중간 문자를 건너뛰어 만든 문자열은 접두사가 아니다. 어떤 문자열이 서로 다른 두 개 이상의 예약 기록에 적힌 코드의 접두사라면 그 문자열을 공통 안내 구간이라고 부른다. 두 기록의 코드 내용이 완전히 같아도 기록의 줄 번호가 다르면 서로 다른 예약 기록이다. 따라서 같은 코드가 두 번 기록되었다면 그 코드 전체가 공통 안내 구간이 될 수 있다. 반면 하나의 기록만으로는 공통 안내 구간을 만들 수 없다. 병원은 모든 공통 안내 구간 중 길이가 가장 긴 문자열을 찾는다. 가장 긴 문자열이 여러 개라면 사전순으로 가장 앞선 문자열 하나를 선택한다. 사전순은 왼쪽부터 처음으로 다른 문자를 비교하여 알파벳에서 앞선 문자를 가진 문자열이 먼저 오는 순서다. 한 문자열이 다른 문자열의 접두사라면 더 짧은 문자열이 먼저 온다. 예약 기록의 개수 N과 각 기록의 코드가 주어진다. 병원이 선택할 공통 안내 구간을 구한다. 모든 기록의 첫 문자가 서로 다르거나 기록이 하나뿐인 경우처럼, 조건을 만족하는 문자열이 없을 수도 있다. 이 경우에는 대문자 코드와 구분할 수 있도록 하이픈 한 개를 출력한다. 선택한 구간이 나타나는 기록의 번호나 개수는 출력하지 않는다.

입력

첫째 줄에 예약 기록의 개수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 20,000이다.
다음 N개의 줄에는 예약 코드가 한 줄에 하나씩 주어진다. 각 코드는 알파벳 대문자 A부터 Z까지만 사용하며 길이는 1 이상 12 이하이다. 같은 코드가 여러 줄에 나타날 수 있다.

출력

길이가 가장 긴 공통 안내 구간을 한 줄에 출력한다. 길이가 같은 후보가 여러 개라면 사전순으로 가장 앞선 것을 출력한다. 공통 안내 구간이 없다면 -를 출력한다.

5
MARBLE
MARKET
SILVER
SIMPLE
MAP

MAR

4
BETA
BETAX
ALTO
ALTAR

BETA

3
A
B
C

-

출처: Devin.KR 자체 제작