Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2828
Auto Spell Corrector

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Have you ever used Microsoft Word (R) to edit English document? Have you noticed the auto-spell-corrector?

Littleboy found that whenever he mistypes the "the" as "teh" or "hte", it will be corrected automatically. Littleboy noticed that people are prone to typing the characters out of order when they type too fast, and he guesses that auto-spell-corrector in Microsoft Word (R) relies on this fact. Being interested in this, he decided to write a simple auto-spell-corrector of his own.

His algorithm works as follow: given a word,

1. If the word can be found from the predefined dictionary, left it as it was.
2. If swapping one pair of consecutive characters leads to another word that can be found from the predefined dictionary, that word is an option for substitution. If one or more substitution candidates were found, output all of them.
3. If neither of the above schemes can be applied to the word, it must be a name, so left it as it was.

Input

Input consists of multiple test cases. The first line of the input will be a positive number T(0<T<=10), representing the number of the test cases. Then follow T test cases.

The first line of each test case, there will be an integer D(0<=D<=100), the number of the words in the predefined dictionary. Then D words follow, each word in its own line. After the predefined dictionary, there will be an integer Q(0<=Q<=100), the number of the words that littleboy typed. Again, follow Q words, each in its own line. The length of the word(both in predefined dictionary and littleboy typed) is between 1 and 20, inclusive. All words will only consist of lower case letters ('a'..'z').

Output

For each word littleboy typed, output all the substitution candidates(or the word as it was, depending on which scheme the word matches) in one line, sorted by lexicographically ascending order and separated by a comma(','). So for each testcase, there will be Q lines of output.

Separate two consecutive test cases with a blank line, but Do NOT output an extra blank line after the last one.

Sample Input

2
1
the
3
the
teh
hte
6
acbed
acbde
abdce
abced
badce
bcade
3
acbde
abcde
smith

Sample Output

the
the
the

acbde
abced,abdce,acbde
smith


Author: SHEN, Guanghao
Source: Zhejiang University Local Contest 2007, Preliminary
Submit    Status