Description

A cryptarithm is an arithmetic expression where some digits have been “eaten by worms,” and we must determine the missing digits from the remaining ones. Consider a simple example:

$$\begin{aligned} \verb!43#9865#045! \\ +\qquad \verb!8468#6633! \\[-1em]\underline{\kern{8em}} \\ \verb!44445509678! \\ \end{aligned}$$

Here, the character # denotes a missing digit. From the equation, it is easy to see that the two missing digits in the first line are 5 and 3 respectively, and the missing digit in the second line is 5.

Now we add two constraints to the problem:

First, we only consider addition cryptarithms. The addition is in base $n$. The three numbers in the expression each have $n$ digits, and leading zeros are allowed.

Second, all digits have been replaced by letters. We only know which digits are equal; equal digits are represented by the same letter, and different digits by different letters. If the addition is in base $n$, we use the first $n$ uppercase letters of the English alphabet to denote the $n$ distinct digits $0$ to $n - 1$; however, these $n$ letters do not necessarily represent $0$ to $n - 1$ in order. The input guarantees that each of the $n$ letters appears at least once.

$$\begin{aligned} \verb!BADC! \\ +\quad \verb!CBDA! \\[-1em]\underline{\kern{4em}} \\ \verb!DCCC! \\ \end{aligned}$$

The above is a base-4 equation. Clearly, if we let $\verb!ABCD!$ represent 0123 respectively, the equation holds. Your task is: given a base-$n$ addition cryptarithm, determine which digits the $n$ different letters represent so that the addition holds. The input guarantees there is exactly one solution.

Input Format

• The first line contains an integer $n$, the base.
• The second to fourth lines each contain a string of uppercase letters, representing the two addends and the sum, respectively. These 3 strings have no spaces at either end, represent digits from high to low, and each has exactly $n$ characters.

Output Format

Output one line with $n$ integers separated by spaces, representing the digits corresponding to $A, B, \dots$ in order.

5
ABCED
BDACE
EBBAA

1 0 3 4 2

Hint

Constraints:

• For 30% of the testdata, $n \le 10$.
• For 50% of the testdata, $n \le 15$.
• For 100% of the testdata, $1 \le n \le 26$.

Translated by ChatGPT 5