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