Spell Checker with Levenshtein Distance Correction

You are given a dictionary of correctly spelled words and a document containing words. Your task is to implement a spell checker. For each word in the document, if it is already correctly spelled (i.e. it appears in the dictionary), output it as is. If it is misspelled, compute its Levenshtein distance (edit distance) to every word in the dictionary, and output the dictionary word that has the smallest edit distance. In case of ties, select the lexicographically smallest word.

The Levenshtein distance between two words is defined as the minimum number of single-character insertions, deletions, or substitutions required to change one word into the other. The formula is given by:

[ \text{lev}(a,b) = \begin{cases} |a| & \text{if } |b| = 0, \ |b| & \text{if } |a| = 0, \ \min\begin{cases} \text{lev}(a_{1...|a|-1},b) + 1, \ \text{lev}(a,b_{1...|b|-1}) + 1, \ \text{lev}(a_{1...|a|-1},b_{1...|b|-1}) + \mathbb{1}{{a{|a|} \neq b_{|b|}}} \end{cases} & \text{otherwise.} \end{cases} ]

Your solution should read input from standard input (stdin) and write the result to standard output (stdout).

inputFormat

The input consists of the following:

1. An integer n (1 ≤ n ≤ 10,000) representing the number of words in the dictionary.
2. n lines, each containing a dictionary word.
3. An integer m (1 ≤ m ≤ 10,000) representing the number of words in the document.
4. m lines, each containing a word from the document.

Words consist of lowercase English letters only.

outputFormat

Output a single line containing m words separated by a single space. For each word in the document, output either the word itself (if it is in the dictionary) or the closest word from the dictionary according to the Levenshtein distance rule. In case of a tie in distance, output the lexicographically smallest word.

3
apple
banana
cherry
2
apple
banana

apple banana