Kattis

# Boxed Letters

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