Отсортируй меня
Мы знаем стандартный алфавитный порядок английских букв и можем использовать его для сортировки слов или других последовательностей. Например, следующие слова отсортированы:
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.