Сортуй мене
Ми знаємо звичайний алфавітний порядок англійського алфавіту і можемо сортувати слова або інші послідовності літер. Наприклад, ці слова відсортовані:
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.
Ручне (або щупальцеве) оброблення різних алфавітних порядків кожного року є виснажливим. Ваше завдання — реалізувати сортування з англійськими літерами у вказаній послідовності.
Вхідні дані
Вхід міститиме один або більше наборів даних. Кожен набір даних починатиметься з рядка, що містить ціле число n і рядок s, де s є перестановкою англійського верхнього регістру алфавіту, що використовується як алфавіт Горелліан у наступному році. Наступні n рядків (1 ≤ n ≤ 20) міститимуть по одному непорожньому рядку літер. Довжина кожного рядка не перевищуватиме 30. Після останнього набору даних йде рядок, що містить лише 0.
Вихідні дані
Перший рядок виходу кожного набору даних міститиме "year ", за яким слідує номер набору даних, починаючи з 1. Решта n рядків — це n вхідних рядків, відсортованих, припускаючи, що алфавіт має порядок у s.