Blaze sends movement orders to his troops, gathered from the inhabitants of one of the shadows. Unfortunately, they don't understand Amber, so Blaze has to send them messages in their own language.
Therein lies the problem: the Amberian prince does not know the spelling of this language well, so he sometimes makes mistakes in words, but no more than one mistake in a word.
There are a lot of words in the language, so if at least one letter in a word changes, then its meaning can change dramatically. If the army does not correctly understand the order, then the entire military campaign may fail. Therefore, it is very important for Blaise to check the correct spelling of words. He decided to ask you to help him.
You must create a program that will output in lexicographic order all the possible words that Blaise could have tried to write, given that he could have made a mistake 1 time.
Input
The first line contains numbers n and m - the number of orders given by Blaze and the number of commands understood by his troops, respectively. (1 <= n, m <= 5000)
The next line takes m words as input - commands that Blaze's troops understand.
In the next n lines, words are given as input - orders given by Blaze.
All strings are less than 100.
Output
Print n lines: line number i contains the answer to the problem for Blaze's order number i. Lines that are the answer to this query are displayed on a single line separated by a space.
Example
Input
5 5
is in if on of
it
in
of
ij
op
Output
if in is
if in is on
if of on
if in is
of on
(c) Evgeny Grigoriev