Spell Checker

You are writing a module for a new spell-checking program. Given a dictionary that lists every correct word (in all of its forms), your module must check whether each given word is spelled correctly.

If a word is not in the dictionary, it can be replaced by the dictionary words that can be produced from it using exactly one of the following operations:

• delete one letter from the word;
• replace one letter of the word with an arbitrary letter;
• insert one arbitrary letter into the word.

For every word to be checked, find all of its possible replacements from the dictionary.

The input has two parts.

The first part lists every word in the dictionary, one word per line, and ends with a line containing a single #. All dictionary words are distinct, and there are at most 10000 of them.

The second part lists every word to be checked, one word per line, and also ends with a line containing a single #. There are at most 50 words to be checked.

Every word in the input (both dictionary words and words to be checked) consists only of lowercase letters and is at most 15 characters long.

Print exactly one line for each word to be checked, in the order in which the words appear in the second part of the input.

• If the word is correct (it appears in the dictionary), print the word followed by is correct.
• Otherwise, print the word followed by a colon (:). If there is at least one replacement, follow the colon with a single space and then all possible replacements separated by single spaces, listed in the order in which they appear in the dictionary (the first part of the input). If there is no replacement, print nothing after the colon.