Zig and Zag Word Game

Zig and Zag are playing a word game. Zig says one letter, and Zag must reply with a word that starts with that letter, chosen from a given allowed word list. However, Zag always picks the word that he has said the least number of times. In the event of a tie, the lexicographically smaller word is chosen. It is guaranteed that for every given letter there is at least one valid word from the list.

Input Format: The input begins with an integer K representing the number of distinct words in the allowed list. The next K lines each contain one word. After that, an integer N is given, representing the number of letters Zig provides. The final line contains N letters (separated by spaces or without separation) corresponding to Zig's prompts.

Rules:

• For each letter, consider all allowed words that start with that letter.
• Select the word with the smallest count of previous occurrences.
• If multiple words have the same count, choose the one that is lexicographically smallest.

Output: Output an array (or list) of N words that Zag says, in order.

The solution may involve updating the frequency count of each word as the game proceeds.

Note: All formulas or conditions are described in LaTeX style: For instance, the condition for ambiguity can be represented as: $$\min_{w}\{count(w)\}.$$

inputFormat

The first line contains an integer K representing the number of allowed words.

The next K lines each contain a distinct word.

The following line contains an integer N -- the number of letters from Zig.

The last line contains N characters (letters) which represent Zig's prompts. They may be separated by space or concatenated.

outputFormat

Output one line containing N words separated by spaces, representing the words chosen by Zag in order.

sample

3
apple
apricot
banana
5
a b a a b

apple banana apricot apple banana