Сортуй мене#6386
Ми знаємо звичайний алфавітний порядок англійського алфавіту і можемо сортувати слова або інші послідовності літер. Наприклад, ці слова відсортовані:
ANTLER
ANY
COW
HILL
HOW
HOWEVER
WHATEVER
ZONE
Використовуються стандартні правила для сортування послідовностей літер:
Перші літери йдуть в алфавітному порядку.
Серед рядків з однаковим префіксом, як префікс AN в ANTLER і ANY, вони впорядковуються за першою літерою, яка відрізняється, тут T або Y.
Один цілий рядок може бути префіксом іншого рядка, як HOW і HOWEVER. У цьому випадку довша послідовність йде після коротшої.
Горелліани, на далекому кінці нашої галактики, виявили різні зразки англійського тексту з наших електронних передач, але не знайшли порядок нашого алфавіту. Будучи дуже організованим і впорядкованим видом, вони хочуть мати спосіб впорядкування слів, навіть у дивних символах англійської. Тому вони повинні визначити свій власний порядок. На жаль, вони не можуть домовитися, і кожен рік Горелліани сперечаються і вирішують новий порядок.
Наприклад, якщо вони погоджуються на алфавітний порядок
UVWXYZNOPQRSTHIJKLMABCDEFG
тоді наведені вище слова будуть відсортовані як
WHATEVER
ZONE
HOW
HOWEVER
HILL
ANY
ANTLER
COW
Перші літери слів йдуть у їхньому алфавітному порядку. Де слова мають однаковий префікс, перша відмінна літера визначає порядок, тому порядок йде ANY, потім ANTLER, оскільки Y передує T у їхньому виборі алфавіту. Все ж HOWEVER йде після HOW, оскільки HOW є префіксом HOWEVER.
Ручне (або щупальцеве) оброблення різних алфавітних порядків кожного року є виснажливим. Ваше завдання — реалізувати сортування з англійськими літерами у вказаній послідовності.
Вхід міститиме один або більше наборів даних. Кожен набір даних починатиметься з рядка, що містить ціле число і рядок , де є перестановкою англійського верхнього регістру алфавіту, що використовується як алфавіт Горелліан у наступному році. Наступні рядків (1 \le n \le 20) міститимуть по одному непорожньому рядку літер. Довжина кожного рядка не перевищуватиме . Після останнього набору даних йде рядок, що містить лише .
Перший рядок виходу кожного набору даних міститиме "year ", за яким слідує номер набору даних, починаючи з . Решта рядків — це вхідних рядків, відсортованих, припускаючи, що алфавіт має порядок у .
Приклад 1