Problem H
Send More Money

Image by Watchara Ritjan (Shutterstock), Used under license

You may have seen puzzles, sometimes called cryptarithmetic puzzles, or simply cryptarithms, that look like this:

The goal of this kind of puzzle is to replace each letter with a (base-$10$) digit so that the resulting arithmetic equality holds. Here are the rules:

• A given letter must always be replaced by the same digit.

• Different letters must be replaced by different digits.

• The leading (leftmost) letter of any word cannot be replaced by 0.

For example, if we try to solve the above puzzle, we find that the following replacements work:

This gives us a correct equality:

Your task is to write a program to solve such puzzles. Note that some cryptarithmetic puzzles are impossible to solve. An example is:

Here the only way to make the equality hold is to replace A with 0, but this violates the rule that the first (and in this case only) letter of any word cannot be replaced by 0.

Also note that some puzzles may have multiple solutions. In this situation, find the solution in which the alphabetically lowest letter is replaced by lowest possible digit, then the second lowest letter is replaced by the lowest possible unused digit, then the third lowest letter is replaced by the lowest possible unused digit, etc. An example is:

Clearly this has more than one solution, but the minimal solution, as described above, is:

Input

The input consists of a line containing a single puzzle. A puzzle is a string of characters of the form $w_1$+$w_2$=$w_3$, where $w1$, $w_2$, $w_3$ are words, and ‘+’ and ‘=’ are the usual “plus” and ”equals” characters (ASCII values $43$ and $61$, respectively). A word is a nonempty string of uppercase letters (A–Z). The maximum length of any puzzle is $100$.

Output

For each puzzle, output a single line containing the minimal solution if the puzzle is solvable, or “impossible” if the puzzle is not solvable. Note that a solution must contain exactly the same number of characters as the corresponding puzzle, with ‘+’ and ‘=’ characters in the same positions as in the puzzle, and all letters replaced by digits (0–9).

SEND+MORE=MONEY

9567+1085=10652

A+A=A

impossible

C+B=A

2+1=3