G. A + B = C
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In search of inspiration for problems, Slava went to scour the vastness of the internet — and found an interesting riddle.

The riddle took the form $$$A + B = C$$$, where the digits of the numbers $$$A$$$, $$$B$$$, and $$$C$$$ were replaced by letters from the Latin (or other) alphabet.

Moreover, three additional rules applied:

  • The numbers in the original identity do not have leading zeros and are not equal to zero.
  • Each letter corresponds to exactly one replaceable digit.
  • Each digit corresponds to exactly one replacing letter.

The solution to such riddles is any substitution "letter — digit" that transforms the expression into an identity.

For the given riddle of the described form, you need to:

  • calculate the number of solutions to this riddle.
  • if there is at least one solution, output any of them.
Input

The first line contains the string $$$SA$$$ $$$(1 \le |SA| \le 3)$$$ — the string corresponding to the number $$$A$$$ in the riddle.

The second line contains the string $$$SB$$$ $$$(1 \le |SB| \le 3)$$$ — the string corresponding to the number $$$B$$$ in the riddle.

The third line contains the string $$$SC$$$ $$$(1 \le |SC| \le 4)$$$ — the string corresponding to the number $$$C$$$ in the riddle.

It is guaranteed that the strings $$$SA$$$, $$$SB$$$, and $$$SC$$$ consist only of uppercase Latin alphabet letters.

Output

In the first line, output an integer $$$R$$$ $$$(0 \le R \le 10^9)$$$ — the number of solutions to this riddle.

If $$$R \gt 0$$$, then in the next three lines output any of the solutions to the riddle:

  • the number $$$A$$$, represented by the string $$$SA$$$;
  • the number $$$B$$$, represented by the string $$$SB$$$;
  • the number $$$C$$$, represented by the string $$$SC$$$.
Examples
Input
ABC
DEF
AAAZ
Output
72
123
987
1110
Input
AAA
BBB
CDC
Output
0
Input
PQ
ST
PV
Output
0
Input
X
Y
X
Output
0
Note

First test example

The riddle ABC + DEF = AAAZ can be solved, for example, as $$$123 + 987 = 1110$$$:

  • $$$A$$$ corresponds to $$$1$$$;
  • $$$B$$$ corresponds to $$$2$$$;
  • $$$C$$$ corresponds to $$$3$$$;
  • $$$D$$$ corresponds to $$$9$$$;
  • $$$E$$$ corresponds to $$$8$$$;
  • $$$F$$$ corresponds to $$$7$$$;
  • $$$Z$$$ corresponds to $$$0$$$.

Examples of other possible solutions:

  • $$$147 + 963 = 1110$$$;
  • $$$167 + 948 = 1115$$$.

Second test example

The riddle AAA + BBB = CDC has no solutions, as in this case

  • either the same digit corresponds to two letters $$$C$$$ and $$$D$$$;
  • or at least two different digits correspond to the same letter ($$$A$$$ or $$$B$$$).

Third test example

The riddle PQ + ST = PV has no solutions, as in this case the number represented by ST must have a leading zero, which is not allowed.

Fourth test example

The riddle X + Y = X has no solutions, as in this case the number represented by Y must equal zero, which is not allowed.