The so-called "insect-eating calculation" means that part of the original calculation formula was eaten by insects, and we need to compute the missing letters based on the remaining numbers. Let's look at a simple example:
The character #
represents the number was eaten by the insects. According to the formula, we can easily conclude: the two numbers in the first summand are and , respectively, and the number in the second summand is .
Now, we make two constraints on the problem:
First, we only consider the insect-eating calculation of addition. The addition here is addition in base , and the three numbers in the formula have exactly digits, and leading 0s are allowed.
Secondly, the insects have eaten up all the numbers. We only know which numbers are the same. We represent the same numbers with the same letters and different numbers with different letters. If the formula is in base , we take the first capital letters of the English alphabet to represent the different numbers from to in the formula: but it is not always the case that A
corresponds to , B
corresponds to , etc. The input data guarantees that each of the letters appears at least once.
The above formula is a formula in base . Obviously, as long as we let A,B,C,D represent , respectively, the equality holds. Your task is, for a given addition formula in base , to find the numbers represented by different letters so that the addition formula is established. The input data is guaranteed to have exactly one solution.
Input Specification
The first line of the input contains a positive integer . In the following three lines, each line consists of a string of upper-case English letters denoting the summands and the sum. There are no spaces on the left or on the right of the string. The numbers are given from the most significant bit (on the left) to the least significant bit. The lengths of the 3 strings are exactly .
Output Specification
Output a line denoting the correspondence between the letters and digits: you should output integers separated by a single space denoting the digits corresponding to .
Sample Input
5
ABCED
BDACE
EBBAA
Sample Output
1 0 3 4 2
Constraints
- For of test cases, .
- For of test cases, .
- For all test cases, .
Comments