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:
- One letter is missing (e.g., letter is written leter) or too much (e.g., letter is written lettter).
- One letter is wrong (e.g., letter is written ketter)
- The order of two adjacent letters is wrong (e.g., letter is written lettre)
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.