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.
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.
For each of the M message words in the input, your program should output a single line:
9 i apple far mat job for then may apply 6 may i apple fur the jpb
may i apple for ? job
The score for each input scenario will be 100% if a correct answer is written to the output file, and 0% otherwise.