Party Games

You've been invited to a party. The host wants to divide the guests into two teams for party games, with exactly the same number of guests on each team. As she greets each guest on arrival, she wants to tell which team the guest is on, as easily as possible, without having to look up each name on a list.

Being a good computer scientist, you have an idea: give her a single string, and all she has to do is compare a guest's name alphabetically to that string. To make this even easier, the string should be as short as possible.

Given the distinct names of $n$ party guests (where $n$ is even), find the shortest possible string $S$ such that exactly half of the names are less than or equal to $S$ and exactly half are greater than $S$. If several strings share the same shortest length, choose the alphabetically smallest one among them.

(All string comparisons are alphabetical.)

The input may contain multiple test cases.

Each test case begins with an even integer $n$ ($2 \le n \le 1000$) on its own line.

The next $n$ lines each contain one name. Each name is a single word consisting only of capital letters and is at most $30$ letters long. Within a test case, the names are distinct.

The input ends with a line containing $0$.

For each test case, print on its own line the shortest possible string the host could use to separate her guests, with ties broken in favor of the alphabetically smallest string. The printed strings consist entirely of capital letters.