Boxed Letters

/problems/boxedletters/file/statement/en/img-0001.png
An example of the NY Times “Boxed Letters” Puzzle. This sample corresponds to sample input $1$.

The New York Times publishes a puzzle called “Boxed Letters” for puzzle enthusiasts. In this puzzle, $12$ letters are shown along the $4$ sides of a box. The task is to find words that are spelled when these letters are connected, subject to the following rules:

  • You may start the first word with any of the letters

  • Consecutive letters in one word cannot be from the same side

  • Words must be at least 3 letters long

  • Letters can be reused

  • The last letter of a word becomes the first letter of the next word, e.g. THY > YES > SINCE

  • All letters must be used

  • Use as few words as possible

After trying the puzzle for a while, you remember that there are dictionaries that should make this task simple.

Can you write a program that solves a Boxed Letters puzzle given a dictionary of words?

Input

The input consists of a single test case, which starts with an integer $n$ ($1 \le n \le 72\, 000$), the size of the dictionary. This line is followed by $n$ lines, each containing a dictionary word of $l$ uppercase English letters ($3 \le l \le 22$). All dictionary words are distinct. The next $5$ lines contains the letters around the box in compressed form. The first line contains the top row, the last line the bottom row. The first character on each of the $3$ lines in between corresponds to the box’s left side, the second character corresponds to the box’s right side. All $12$ characters are distinct uppercase English letters.

Output

Output a word list that solves this puzzle, in the order in which the words would be entered into the puzzle. Place each word on a separate line. If there are multiple word lists that satisfy the conditions, you may output any of them. You are guaranteed that a solution exists.

Sample Input 1 Sample Output 1
22
DATUM
TRUMAN
STAINS
INSTANTS
TACITUS
LINUS
TANTRUMS
MCADAM
ILLICIT
ALUM
CARINA
DRUMSTICKS
BACILLI
SUBURBAN
TIC
SALSA
TALIBAN
ATTAIN
LUNATIC
ASIATICS
MANDARIN
RUMINANTS
R I N
M D
C S
A B
U T K
DRUMSTICKS
SUBURBAN