Cryptarithmetic Puzzle
You are given three strings
a, b, and c. Your task is to assign a digit to each character in such a way that the equation a + b = c holds. It is guaranteed that a valid digit assignment solution exists for the given strings.A digit assignment is valid if it satisfies the following conditions:
- Each character in the strings
a,b, andcrepresents a unique digit from 0 to 9.
- The resulting numbers should not have leading zeroes, except the number 0 which consists of one zero digit.
Input
The input consists of three lines, each containing a string. The strings
a, b, and c consist only of lowercase English letters, and their lengths are between 1 and 15 (inclusive).It is guaranteed that a valid digit assignment solution exists for the given equation.
Output
Print the three respective numbers in the same order.
If there are multiple valid digit assignments that satisfy the equation, you can output any of the valid solutions.
Examples
Input | Output |
send
more
money | 9567
1085
10652 |
a
b
b | 0
3
3 |
Constraints
Time limit: 8 seconds
Memory limit: 512 MB
Output limit: 1 MB