Source file: automatic.(c|cc|hs|java|pas)
Input file: automatic.in
Some text editors offer a feature to correct words which seem to be written incorrectly. In this problem you are asked to implement a simple Automatic Correction of Misspellings (ACM).
ACM takes care of the following misspellings of words:
ACM is based on a dictionary of known words. When a text contains a word which is not in the dictionary, ACM will try to replace it by a similar word of the dictionary. Two words are similar if we can transform one word into the other by doing exactly one of the misspellings listed above. An unknown word is left unchanged if there is no similar word in the dictionary.
The first line of the input file will give the number n of words in the dictionary (n ≤ 10000). The next n lines contain the dictionary words. The following line contains an integer q ≤ 1000, the number of query words. The next q lines contain the query words. You may assume that each word in the input consists of 1 to 25 lower case letters ('a' to 'z').
For each query word, print one line with the query word followed by one of the following possibilities:
10 this is a dictionary that we will use for us 6 su as the dictonary us willl
su is a misspelling of us as is a misspelling of is the is unknown dictonary is a misspelling of dictionary us is correct willl is a misspelling of will