AIOC Banner

Problem: ABC

Want to try solving this problem? You can submit your code online if you log in or register.


ABC...


Time Limit: 5 seconds
Memory Limit: 32 MB

Despite your best efforts, your writing is riddled with typos. You are constantly trying to improve, but it is hard work. Luckily, you have just come up with a brilliant solution – you will write a computer program to correct misspelt words!

Your "misspell checker" must be able to take a dictionary of valid words and a message, and correct all the typos. For the purposes of this problem, a typo is a word not in the dictionary which, by replacing a single letter with a different letter, becomes a valid word.

Input

The first line of input will contain a single integer N, indicating the number of words in the dictionary (1 ≤ N ≤ 100,000). Each of the next N lines will contain a single distinct dictionary word. The next line of input will contain a single integer M, indicating the number of words in the message (1 ≤ M ≤ 10,000). Each of the next M lines will contain a single word to be checked. All words will consist of between 1 and 20 lower-case letters, inclusive.

For 30% of the available marks, N,M ≤ 1000. For 60% of the available marks, N ≤ 30,000.

Output

For each of the M message words in the input, your program should output a single line:

Sample Input

9
i
apple
far
mat
job
for
then
may
apply
6
may
i
apple
fur
the
jpb

Sample Output

may
i
apple
for
?
job

Scoring

The score for each input scenario will be 100% if a correct answer is written to the output file, and 0% otherwise.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 24 May 2019,  3:20am AEST