The Killer Word (Large)

You are playing Hangman with your friend Sean, and Sean is not very good at this game. Take advantage of his crude strategy and make him lose as many points as possible.

 +--+
 |    O
 |   / | \       Mystery word: _ a _ a _ a _
 |    /  \
 |
+-+---+

Hangman is played as follows.

• There is a dictionary D of all valid words, and both you and Sean know it. A word consists only of the characters a to z, with no spaces.
• You begin by choosing any word from D and writing it on a blackboard with each letter replaced by a single blank _.
• On his turn, Sean picks a letter and asks whether it is in the word. If it is, you reveal all positions of that letter. If it is not, Sean loses one point.
• Once every letter of the word has been revealed, the round ends.
• The round never ends before that, no matter how many points Sean loses.

Sean uses a very simple strategy. He makes a list L of the 26 letters in some order and walks through it one letter at a time. If D contains at least one word that (a) has the letter he is looking at and (b) is consistent with what is written on the blackboard and with the results of all of his previous questions, then Sean asks about that letter. Otherwise he skips it. Either way, Sean moves on to the next letter in the list.

Given Sean's list, find the word you should choose to make Sean lose as many points as possible. If several choices make him lose the same number of points, choose the word that appears first in D.

Worked walkthrough

Suppose L is "abcdefghijklmnopqrstuvwxyz" and D consists of banana, caravan, and pajamas. If you choose pajamas, the game plays out like this.

• You write 7 blanks _ _ _ _ _ _ _ on the blackboard. From the number of blanks alone, Sean knows the word is either caravan or pajamas.
• Sean asks about a, the first letter of L, and you reveal every position of a, so the blackboard becomes _ a _ a _ a _.
• Sean skips b even though banana uses it, because he already knows that word is not your answer.
• He then asks about c, since caravan has one. The word you actually chose has no c, so Sean loses one point and nothing new is revealed.
• Only one candidate is left, so Sean knows the answer is pajamas and asks about j, m, p, and s in order, ending the round without losing another point.

So Sean loses one point if you choose pajamas. He would have lost nothing on either of the other two words.

The first line contains the number of test cases T. T test cases follow. The first line of each test case contains the number of words in the dictionary N and the number of lists to consider M.

The next N lines contain the words of the dictionary $D_1, D_2, \dots, D_N$, one per line. Each word is an arbitrary sequence of the characters a to z.

The final M lines contain the lists Sean will use, $L_1, L_2, \dots, L_M$, one per line. Each list is 26 characters long and contains each letter exactly once. Sean asks about letters in the order given by the list, exactly as described above.

Limits

• $1 \le T \le 10$
• Each word in the dictionary has between 1 and 10 characters.
• No word appears twice within a single test case.
• $1 \le N \le 10000$
• $1 \le M \le 100$

For each test case, output one line of the form Case #x: w1 w2 ... wM, where x is the test case number starting from 1 and wi is the word you should choose when Sean asks about letters in the order of $L_i$. Separate the words with single spaces. If several words make Sean lose the same number of points, output the one that appears first in the dictionary.