A word of the MIU language is a string built using just the characters M, I and U, that can be generated by transforming the initial string MI by means of repeatedly applying any of the following three rules, subject to a restriction described below:
The restriction mentioned above is that rule 1 may not be applied after rules 2 or 3 have ever been applied.
Write a program that determines whether a given string built only from the letters M, I and U belongs to the MIU language, and, in that case, list a minimal length sequence of strings that show all intermediate steps in the transformation sequence. Such a sequence is called a "minimal derivation". If there are several possible minimal derivations, your program should choose, among those, the one that at each step leads to the least (in the lexicographical order) next string.
The input consists of a single line containing the string to be checked.
If the input does not correspond to a string in the MIU language, the output should consist of the single word "no". Otherwise, the output should contain a sequence of strings, one string per line, presenting a minimal derivation as specified above.