77377

Interview

Time limit1sMemory limit128 MB

Summary

Split a digit string into dictionary words whose telephone-keypad encoding matches each segment.

Level: Medium5 of 10
Topics: Dynamic programming, Trie, String
Solved: No attempts yet

Problem

International Cellular Phones Corporation (ICPC) is betting its future on a new mobile phone that will ship with a web browser, a mailer, an instant messenger, and many other communication tools. If the people at ICPC cannot finish this hard job, the company loses its market share.

Your job is to build the text input software for the small terminal. Most phones today have twelve buttons: ten number buttons from "0" to "9" and two special buttons, "*" and "#". The company is ambitious, but it decided to follow today's standards and conventions. You may not change the standard button layout, and you must respect the standard button assignment below.

button	letters	button	letters
2	a, b, c	6	m, n, o
3	d, e, f	7	p, q, r, s
4	g, h, i	8	t, u, v
5	j, k, l	9	w, x, y, z

Only eight buttons are left for text input.

Users of current ICPC phones are in such a rush that they grudge even one extra button press. Your software must therefore spend a single button press per character. The sequence of button presses "77377" has to produce the word "press", and "77377843288866" has to produce "press the button".

This looks impossible, because one digit stands for more than one English letter. "77377" alone represents not only "press" but any one of $768 = 4 \times 4 \times 3 \times 4 \times 4$ strings. The good news is that the new model has enough memory to hold a dictionary, so you can write a program that filters out the strings the dictionary does not list.

Input

The input consists of several data sets. Each data set holds one dictionary and one sequence of button presses in the following format.

n
word1
...
wordn
sequence

n on the first line is a positive integer, the number of words in the dictionary. Each of the next n lines holds one word, written with lower case letters from 'a' to 'z' only. The words appear in arbitrary order, not necessarily lexicographic order. No word occurs twice in the dictionary. The last line, sequence, is the sequence of button presses, and it contains digits from '2' to '9' only.

A dictionary holds at most 100 words, and the length of each word is between 1 and 50, inclusive. The number of digits in sequence is between 1 and 300, inclusive.

A line containing a single zero ends the input.

Output

For each data set, print every sentence that the given sequence of button presses can spell. A sentence is a sequence of words from the dictionary, and each sentence goes on its own line.

Two adjacent words on a line are separated by a single space, and the last word is followed by a single period ('.').

Print the sentences in this order: a sentence with fewer words comes first, and among sentences with the same number of words, the one whose whole line, period included, comes earlier in ASCII order is printed first.

After the sentences, print a terminating line that holds two hyphens ("--") and nothing else. If no sentence can be spelled, print only that terminating line.

For each data set the number of printed sentences is at most 20, not counting the terminating line.

Examples1

Example 1

Input

5
push
press
the
button
bottom
77377843288866
4
i
am
going
go
42646464
3
a
b
c
333
0

Expected output

press the button.
--
i am going.
i am go go i.
--
--