Roman Numerals

The original system of writing numbers used by the early Romans was simple but cumbersome. Various letters were used to represent important numbers, and these were strung together to represent other numbers, with the values decreasing monotonically from left to right. The letters they used and the values they represented are given in the table below.

Thus 1993 was written as MDCCCCLXXXXIII. This system was later superseded by a partially place-oriented system: whenever the rule of decreasing values was broken, the immediately preceding (smaller) value was treated as negative and subtracted from the following (out-of-place) larger value. In this system 1993 was usually written as MCMXCIII. There is still some controversy about which letters may precede which, but for this problem we assume the following restrictions:

• A letter from the left column may never appear more than three times in a row, and there may be at most one further occurrence of that letter.
• A letter from the right column may never appear more than once.
• Once a letter has been used in a "negative" position, every following character (except the one immediately after it) must not be greater than that character.

Thus we may write MXMIII for 1993, or CCXCIV for 294; however we may not write ILV for 54, nor LIL for 99. Note that 299 may be written as CCXCIX or CCIC.

Given a Roman sum, we can interpret it either literally or as an encoding of an Arabic (base-10) sum in which every distinct letter stands for a single decimal digit. For example, V+V=X can be read as an encoding of an Arabic sum with $V \in \{1,2,3,4\}$ and $X = 2V$, so it is ambiguous. Similarly, X+X=XX is a correct Roman sum but an impossible Arabic encoding (other than the forbidden trivial X = 0), and XX+XX=MXC is an incorrect Roman sum yet a valid encoding with M = 1, X = 9, and C = 8.

Write a program that reads sums written in Roman numerals and, for each one, determines whether it is correct as a Roman sum and whether it is impossible, ambiguous, or valid as an Arabic encoding. Assume that zero never appears on its own or as a leading digit, and that no two Roman letters map to the same Arabic digit.

Input consists of a series of lines. Each line contains an apparent Roman sum: a valid Roman number, a plus sign (+), another valid Roman number, an equals sign (=), and a third valid Roman number. No Roman number contains more than 9 letters. The input is terminated by a line containing a single # character.

For each input line, output one line containing exactly two words separated by a single space. The first word is Correct if the Roman sum is correct and Incorrect otherwise. The second word is impossible, ambiguous, or valid, according to the Arabic encoding.