파티 게임

파티에 초대받았다. 주최자는 손님을 인원수가 똑같은 두 팀으로 나눠 게임을 진행하려고 한다. 손님이 도착할 때마다 명단을 찾아보지 않고 바로 팀을 알려 주고 싶어서, 문자열 하나를 미리 정해 두고 손님 이름이 그 문자열보다 사전순으로 앞인지 뒤인지만 보고 팀을 나누기로 했다.

서로 다른 손님 이름 n개가 주어진다. n은 짝수다. 이름 중 정확히 절반이 $S$보다 작거나 같고 나머지 절반이 $S$보다 크게 되는 가장 짧은 문자열 $S$를 구하라. 그런 문자열이 가장 짧은 길이에서 여러 개면 사전순으로 가장 앞선 것을 답으로 한다.

문자열 비교는 사전순으로 한다. 한 문자열이 다른 문자열의 앞부분과 완전히 같으면 짧은 쪽이 앞선다. 예를 들어 FRED는 FREDDIE보다 앞선다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에 짝수 n ($2 \le n \le 1000$)이 주어진다. 이어지는 n개 줄에 이름이 한 줄에 하나씩 주어진다. 이름은 대문자로만 이루어진 한 단어이고, 길이는 1자 이상 30자 이하다. 한 테스트 케이스 안의 이름은 모두 서로 다르다. 입력의 마지막 줄에는 0이 하나 주어진다.

각 테스트 케이스마다 손님을 나눌 수 있는 가장 짧은 문자열 중 사전순으로 가장 앞선 것을 한 줄에 출력한다. 문자열은 대문자로만 출력하고 공백은 넣지 않는다. 테스트 케이스 사이에 빈 줄을 넣지 않는다.