Hide

Problem D
Low Toner

You have a printer with a toner cartridge that’s just about empty. When you print a document, some letters may not print very well, and it may be easy to mistake one letter for another. For example, a printed letter that looks as a P may be the result of trying to print an R and the leg failing to print. However, a printed character that looks like an R must really be an R. Your toner shortage might fail to print parts of letters, but it never prints parts that it shouldn’t. The following chart illustrates all of the possible misprintings of letters. Additionally, if any letter fails to print entirely, it shows up as a space.

\includegraphics[width=0.5\textwidth ]{graph}

To help you read these printouts, you want a program to figure out the possible words or phrases that could have produced a particular printed line. This task is aided by a dictionary. We assume that any printed line is the result of printing a sequence of dictionary words with one space between consecutive words. Thus, a printout that looks like “FFFF” could be the result of printing “BEEF” or “BEEP”, but not “PBFE” since the first two are legal words but the third is not.

Input

Input begins with a copy of the dictionary. This starts with a number, $1 \le N \le 20\, 000$ and is followed by $N$ lines, each containing a word from the dictionary, given in lexicographic order. This is followed by up to $100$ test cases, one per line, up to end of file. Each test case contains up to $200$ characters (using only spaces and uppercase letters A-Z). All dictionary words are up to $20$ uppercase (A-Z) letters.

Output

For each test case, print all possible sequences of space-separated dictionary words that could print out like the test case. Print your results one per line and in lexicographic order. Print a single blank line between the outputs for consecutive test case.

Sample Input 1 Sample Output 1
5
BEEF
BEEP
CONNECT
CONNECTICUT
CUT
FFFF
CC NECI CUT
BEEF
BEEP

CONNECT CUT
CONNECTICUT

Please log in to submit a solution to this problem

Log in