Задачи
Sort Me
Sort Me
Нам известен порядок букв в английском алфавите, поэтому мы можем сортировать слова или другие последовательности букв. Например, следующие слова являются отсортированными:
\textbf{ANTLER}
\textbf{ANY}
\textbf{COW}
\textbf{HILL}
\textbf{HOW}
\textbf{HOWEVER}
\textbf{WHATEVER}
\textbf{ZONE}
Приведем стандартные правила сортировки последовательностей букв:
\begin{enumerate}
\item Первые буквы слов расположены в алфавитном порядке.
\item Для строк с одинаковым префиксом, как например префикс \textbf{AN} в \textbf{ANTLER} и \textbf{ANY}, упорядочение происходит по первому несовпадающему символу, в данном случае \textbf{T} и \textbf{Y}.
\item Одно слово может быть префиксом другого, как например \textbf{HOW} и \textbf{HOWEVER}. Тогда более длинное слово следует за коротким.
\end{enumerate}
The Gorellians, at the far end of our galaxy, have discovered various samples of English text from our electronic transmissions, but they did not find the order of our alphabet. Being a very organized and orderly species, they want to have a way of ordering words, even in the strange symbols of English. Hence they must determine their own order. Unfortunately they cannot agree, and every Gorellian year, they argue and settle on a new order.
For instance, if they agree on the alphabetical order
\textbf{UVWXYZNOPQRSTHIJKLMABCDEFG}
then the words above would be sorted as
\textbf{WHATEVER}
\textbf{ZONE}
\textbf{HOW}
\textbf{HOWEVER}
\textbf{HILL}
\textbf{ANY}
\textbf{ANTLER}
\textbf{COW}
The first letters of the words are in their alphabetical order. Where words have the same prefix, the first differing letter determines the order, so the order goes \textbf{ANY}, then \textbf{ANTLER}, since \textbf{Y} is before \textbf{T} in their choice of alphabet. Still \textbf{HOWEVER} comes after \textbf{HOW}, since \textbf{HOW} is a prefix of \textbf{HOWEVER}.
Dealing with the different alphabetical orders each year by hand (or tentacle) is tedious. Your job is to implement sorting with the English letters in a specified sequence.
\InputFile
Состоит из нескольких тестов. Each dataset will start with a line containing an integer \textbf{n} and a string \textbf{s}, where \textbf{s} is a permutation of the English uppercase alphabet, used as the Gorellians' alphabet in the coming year. The next \textbf{n} lines (\textbf{1} ≤ \textbf{n} ≤ \textbf{20}) will each contain one non-empty string of letters. The length of each string will be no more than \textbf{30}. Following the last dataset is a line containing only \textbf{0}.
\OutputFile
The first line of output of each dataset will contain "\textbf{year} " followed by the number of the dataset, starting from \textbf{1}. The remaining \textbf{n} lines are the \textbf{n} input strings sorted assuming the alphabet has the order in \textbf{s}.
Входные данные #1
8 UVWXYZNOPQRSTHIJKLMABCDEFG ANTLER ANY COW HILL HOW HOWEVER WHATEVER ZONE 5 ZYXWVUTSRQPONMLKJIHGFEDCBA GO ALL ACM TEAMS GO 10 ZOTFISENWABCDGHJKLMPQRUVXY THREE ONE NINE FIVE SEVEN ZERO TWO FOUR EIGHT SIX 0
Выходные данные #1
year 1 WHATEVER ZONE HOW HOWEVER HILL ANY ANTLER COW year 2 TEAMS GO GO ALL ACM year 3 ZERO ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE