# Alphametics

Alphametics is a term coined by J.A.H. Hunter to design those puzzles where letters represent decimal digits that make true a certain mathematical relation. A well known example for this is the puzzle: SEND + MORE MONEY In this context, Alphametic Cryptarithm Masters (ACM) is a recently founded enterprise that is interested on applications of this kind of puzzles to cryptography. For that reason, they want to develop software to solve a reduced family of alphametics in an automated way and you are supposed to help them in this task. Alphametic puzzles of interest to ACM satisfy the following constraints: • Puzzles are stated by means of an arithmetic equation of the form described by the regular expression: ⟨word⟩ (⟨op⟩ ⟨word⟩)∗ = ⟨word⟩ (⟨op⟩ ⟨word⟩)∗ where ⟨word⟩ is a sequence of uppercase characters of the English alphabet, and ⟨op⟩ is any of the operators in the set {+ ,-} . • No more than ten different characters occur in any puzzle. • There will be at least one blank between words, operators and the equality symbol ‘=’ . • Each letter in the puzzle statement stands for a different decimal digit 0 , . . . , 9 . • Each word represents a decimal number. • + and - operators stand for the usual addition and substraction operations. • Numbers represented by words cannot begin by leading zeroes. We say that a word representing a number begins with a leading zero if it has at least two characters and its left-most character represents zero. A solution for an alphametic puzzle is a value assignment for the letters in the words of the puzzle statement, such that the equation is satisfied. Input The problem input consists of several cases, each one defined by a line with the puzzle statement as described above. It is guaranteed that every problem statement is well formed. The end of the input corresponds to the end of the input file. Output Output texts for each input case are presented in the same order that the input is read. For an input case in the puzzle statement, the output should be a ten character expression ⟨c0⟩⟨c1⟩ · · · ⟨c9⟩ where ⟨ck⟩ is the letter of the statement whose value is the digit k. If the digit k is not assigned to any letter, ⟨ck⟩ should be an asterisk, so the given assignment is a solution for the puzzle instance. If such a solution does not exist, a line with ten asterisks should be written.

2/2 Sample Input SEND + MORE = MONEY CONTEST + ACM = ACIS + ACM + CONTEST VIOLIN + VIOLIN + VIOLA = TRIO + SONATA Sample Output OMY**ENDRS

AVTSLROIN*