Closest Dictionary Word

Given a dictionary of words and a list of query words, your task is to find for each query word the word from the dictionary that has the smallest Levenshtein distance to it. The Levenshtein distance between two strings (s) and (t) is defined as the minimum number of single-character edits (insertions, deletions, or substitutions) required to change (s) into (t). If a query word exactly matches a dictionary word, it is considered its own closest match with distance 0. In case of ties – i.e. when multiple dictionary words have the same minimum distance – return the one that appears first in the dictionary. If the dictionary is empty, output "None" for that query word. Note that if the list of query words is empty, no output should be produced.

inputFormat

The input is read from standard input (stdin) in the following format:

• The first line contains an integer (N), representing the number of words in the dictionary.
• The next (N) lines each contain a single dictionary word.
• The following line contains an integer (M), representing the number of query words.
• The next (M) lines each contain a single word that needs to be checked.

outputFormat

Output (M) lines to standard output (stdout). Each line should contain the closest matching word from the dictionary corresponding to each query. If the dictionary is empty, output the string "None" for that query.## sample

3
apple
banana
carrot
1
apple

apple