We want to develop an automatic spelling corrector. The spelling corrector should detect words that are not present in its dictionary, and replace them with the nearest one. The distance between an input word and a dictionary word is computed taking into account dele- tions, insertions and substitutions of characters: an inserted or deleted character is penalized with 3 points, a character substitution is penalized with 5 points, while matches are not penalized. Each word can have from 1 to 9 characters. Only the lowercase characters from ‘a’ to ‘z’ are allowed. If multiple words in the dictionary have the same distance to the input word, they should be ranked in lexicographic order and the first one should be selected. Input The input will contain several test cases, each of them as described below. Consecutive test cases are separated by a single blank line. The first line in the input contains an integer n specifying the number of words in the dictionary. The following n lines contain the dictionary: one word per line. The dictionary is sorted in lexicographic order. The dictionary is followed by a line containing m, the number of words of text. The text consists of lines of 10 words separated by white space, except the last one that can have less words. Output For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. The output consists of the corrected text: m words, presented in lines with 10 words, except the last one that can be shorter. Sample Input 5 ate carrot rabbit the white 6 the white rabit ate ate carott 20 a abbey adapted ago almost but clumsy had
2/2 he joined living manuel monk not of that the to way year 22 the clumsy momk manuel had joined the abey almost a year ago but he had not adapted to that way of leaving Sample Output the white rabbit ate ate carrot the clumsy monk manuel had joined the abbey almost a year ago but he had not adapted to that way of living