Canadian Computing Competition: 1998 Stage 2, Day 2, Problem 2

In a word processing accident, all the spaces were removed from a file containing lines of English text. Your job is to replace the spaces in the text.

Input Specification

Your input consists of two parts: a dictionary, and a number of lines of text with no spaces. The dictionary is preceded by an integer, ~n < 1000~, indicating the number of words in it, followed by the words, one per line. Following the dictionary is another integer, ~m < 1000~, and ~m~ lines of text with no spaces.

No line will be longer than ~100~ characters. The input contains only lowercase letters. No word in the dictionary exceeds ~20~ letters.

Output Specification

Insert spaces into each line so that it is composed of a sequence of words from the dictionary. If there is more than one way to break the line into words, output the solution with the fewest words (or one of the solutions if there are many). If there is no way to break the line into words, print *** followed by the line with no spaces.

Sample Input

5
the
a
cow
there
re
3
therecow
acowrethe
zyzzy

Sample Output

there cow
a cow re the
***zyzzy