Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0087 - SORT ME

   We know the normal alphabetical order of the English alphabet, and we can then sort words or other letter sequences.  For instance these words are sorted:

ANTLER
ANY
COW
HILL
HOW
HOWEVER
WHATEVER
ZONE

   The standard rules for sorting letter sequences are used:

  1. The first letters are in alphabetical  order.
  2. Among strings with the same prefix, like the prefix AN in ANTLER and ANY, they are ordered by the first character that is different, T or Y here. 
  3. One whole string may be a prefix of another string, like HOW and HOWEVER.  In this case the longer sequence comes after the shorter one.

   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

UVWXYZNOPQRSTHIJKLMABCDEFG

   then the words above would be sorted as

WHATEVER
ZONE
HOW
HOWEVER
HILL
ANY
ANTLER
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 ANY,  then ANTLER, since Y is before T in their choice of alphabet.  Still HOWEVER comes after HOW, since HOW is a prefix of 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.

Input

    The input will contain one or more datasets.  Each dataset will start with a line containing an integer n and a string s, where s is a permutation of the English uppercase alphabet, used as the Gorellians' alphabet in the coming year.  The next n lines (1 ≤ n ≤ 20) will each contain one non-empty string of letters.  The length of each string will be no more than 30.  Following the last dataset is a line containing only 0.

Output

    The first line of output of each dataset will contain "year " followed by the number of the dataset, starting from 1.   The remaining n lines are the n input strings sorted assuming the alphabet has the order in s.

Examples

stdin

stdout

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

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


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2014-01-11
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.NA Mid-Central 2013.H

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.