Ігри для вечірок
Вас запросили на вечірку. Господарка хоче поділити гостей на 2 команди для ігор, з однаковою кількістю гостей у кожній команді. Вона прагне визначати, в якій команді знаходиться гість, коли вітає їх при вході, і робити це якомога простіше, без необхідності шукати ім'я кожного гостя у списку. Як досвідчений комп'ютерний науковець, ви пропонуєте таке рішення: дайте їй один рядок, і все, що їй потрібно зробити, це визначити, чи ім'я гостя алфавітно менше або більше цього рядка.
Дано унікальні імена n гостей вечірки (n парне), знайдіть найкоротший можливий рядок S такий, що рівно половина імен менше або дорівнює S, а рівно половина більше S. Якщо існує більше одного рядка найкоротшої довжини, виведіть той, що йде першим за алфавітом.
Вхідні дані
У вхідних даних буде кілька тестових випадків. Кожен тестовий випадок починається з парного цілого числа n (2 ≤ n ≤ 1000) на окремому рядку. На наступних n рядках будуть імена, по одному на рядок. Кожне ім'я буде одним словом, що складається тільки з великих літер, і буде мати щонайменше одну літеру і не більше 30 літер. Усі імена в тестовому випадку будуть унікальними. Вхідні дані закінчуються 0 на окремому рядку.
Вихідні дані
Для кожного випадку виведіть алфавітно перший з усіх найкоротших можливих рядків, які ваша господарка могла б використати для розділення гостей. Виведіть цей рядок, використовуючи всі великі літери. Не виводьте жодних пробілів. Не ставте порожній рядок між виводами.