cho.sh

Party Games

For each test case, find the shortest string that splits the sorted guest names into two equal halves, choosing the alphabetically first if several have that length.

Medium4StringSortingGreedyNo attempts yetTime limit2sMemory limit512 MB

Problem

You have been invited to a party. The host wants to split the guests into two teams of exactly the same size for party games. She would rather not look up each name on a list as the guests arrive, so she plans to fix one string in advance and decide each guest's team by whether the name comes before or after that string alphabetically.

You are given the names of n guests, all different, with n even. Find the shortest string SS such that exactly half of the names are less than or equal to SS and the other half are greater than SS. If more than one string of that shortest length works, report the alphabetically first one.

Strings are compared alphabetically. When one string is exactly the beginning of another, the shorter one comes first, so FRED comes before FREDDIE.

Input

The input holds several test cases. Each test case begins with an even integer n (2≤n≤10002 \le n \le 1000) on its own line. The next n lines hold one name each. Every name is a single word of capital letters, at least 1 and at most 30 letters long. All names inside one test case are different. The input ends with a line holding 0.

Output

For each test case, print on its own line the alphabetically first of all the shortest strings that separate the guests. Print the string in capital letters with no spaces, and print no blank line between test cases.