-261. Puzzle Equation

Task Description

Write a program to solve a puzzle. The puzzle has three strings of upper case letters and digits. Now you need to replace the upper case letters with digits from 1 to 9, so that the product of the first two numbers is the third number. For example, you are given (“ATHF”, “FHTA”, “5HHTAAF”). Now if you replace A with 1, T with 2, H with 3, and F with 4, then you will get (1234, 4321, 5332114), and the product of 1234 and 4321 is indeed 5332114. Note that to make the problem simple, it is not necessary to make the digits for all letters different. For example if you are given (“CD”, “AB”, “242”) then a feasible solution is (22, 11, 242). Also note that we ask for any solution, so (11, 22, 242) is also a solution.

Input

Three nonempty strings consisting of uppercase letters and digits. In order to avoid overflow while multiplying, the sum of lengths of the first two strings will not exceed 9.

Output

An equation that shows the product of the first two string after replacing is indeed the third. If there are multiple solutions, output the any one of them. It is guaranteed that all the test inputs are solvable.

Sample Input 1

ATHF
FHTA
5HHTAAF

Sample Output 1

1234 x 4321 = 5332114

Sample Input 2

CD
AB
242

Sample Output 2

22 x 11 = 242

Hint

The first thing you need to do is to find and collect all the upper case letters in the three strings. After that the second thing you need to do is to try all the 1 to 9 combinations on them, and verify each of them. The problem is designed so that you do not need to do any cut. That is, you can always verify your guesses when all the upper case letters are replced by digits, then convert the strings to integers, then verify the equation. Since the problem asks for any answer, you can stop at the first answer you find.

Notice

若前導為零，請保持輸出，如 001 x 002 = 002，請保持長度相同 by Morris.