파티 게임

당신은 파티에 초대받았습니다. 파티를 주최한 사람은 손님들을 파티 게임을 위해 정확히 같은 인원수의 두 팀으로 나누려고 합니다. 주최자는 손님이 도착해 인사를 나눌 때, 명단에서 이름을 일일이 찾아보지 않고도 그 손님이 어느 팀인지 바로 알 수 있기를 원합니다.

훌륭한 컴퓨터 과학자인 당신은 아이디어를 냅니다. 주최자에게 문자열 하나를 건네주면, 주최자는 손님의 이름을 그 문자열과 사전순으로 비교하기만 하면 됩니다. 이 작업을 더 쉽게 만들기 위해, 이 문자열은 가능한 한 짧아야 합니다.

서로 다른 $n$명(단, $n$은 짝수)의 손님 이름이 주어질 때, 정확히 절반의 이름이 $S$보다 작거나 같고 나머지 절반의 이름이 $S$보다 크도록 하는 가장 짧은 문자열 $S$를 찾으세요. 길이가 같은 가장 짧은 문자열이 여러 개라면, 그중 사전순으로 가장 작은 문자열을 선택합니다.

(모든 문자열 비교는 사전순으로 이루어집니다.)

입력에는 여러 개의 테스트 케이스가 포함될 수 있습니다.

각 테스트 케이스는 짝수 $n$($2 \le n \le 1000$)이 한 줄에 주어지며 시작됩니다.

다음 $n$개의 줄에는 이름이 한 줄에 하나씩 주어집니다. 각 이름은 대문자로만 이루어진 하나의 단어이며 길이는 $30$자를 넘지 않습니다. 한 테스트 케이스 안에서 이름은 서로 다릅니다.

입력은 한 줄에 $0$이 주어지면 끝납니다.

각 테스트 케이스마다, 주최자가 손님을 두 팀으로 나눌 때 사용할 수 있는 가장 짧은 문자열을 한 줄에 출력합니다. 길이가 같은 것이 여러개면 사전순으로 가장 작은 것을 선택합니다. 출력하는 문자열은 모두 대문자로 이루어집니다.