Игры для вечеринок
Вас пригласили на вечеринку. Хозяйка хочет разделить гостей на 2 команды для игр, чтобы в каждой команде было одинаковое количество участников. Она хочет сразу определить, в какой команде находится гость, когда приветствует его по прибытии, и сделать это как можно проще, не тратя время на поиск имени каждого гостя в списке. Будучи хорошим компьютерным ученым, у вас есть идея: предложить ей одну строку, и все, что ей нужно сделать, это определить, меньше или больше этой строки имя гостя в алфавитном порядке.
Даны уникальные имена n гостей вечеринки (n четное). Найдите самую короткую возможную строку S, такую, что ровно половина имен меньше или равна S, и ровно половина больше S. Если существует более одной строки минимальной длины, выведите ту, которая идет первой в алфавитном порядке.
Входные данные
Входные данные содержат несколько тестовых случаев. Каждый тестовый случай начинается с четного целого числа n (2 ≤ n ≤ 1000) на отдельной строке. На следующих n строках будут имена, по одному на строку. Каждое имя — это одно слово, состоящее только из заглавных букв, и будет иметь длину не менее одной буквы и не более 30 букв. Все имена в тестовом случае будут уникальными. Входные данные заканчиваются строкой с 0 на отдельной строке.
Выходные данные
Для каждого случая выведите алфавитно первую из всех самых коротких возможных строк, которые хозяйка могла бы использовать для разделения гостей. Выведите эту строку, используя все заглавные буквы. Не выводите пробелы. Не ставьте пустую строку между выводами.