Day 2 Question 2

Text Segmentation

Input file: text.in

Output file: text.out

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. 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. 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.

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

Sample Input

5
the
a
cow
there
re
3
therecow
acowrethe
zyzzy

Output for Sample Input

there cow
a cow re the
***zyzzy