P5758 [NOI2000] Operator Decoding

Archaeological discoveries show that several thousand years ago, during the ancient Gumei civilization, mathematics was very advanced. They knew multi-digit addition and multiplication, and their expressions and calculation rules were exactly the same as those commonly used today (for example, integers are in decimal, the left side is the higher digit, the highest digit cannot be zero; expressions use infix notation, multiplication before addition, etc.). The only difference is that their symbols were written differently. There is strong evidence that the mathematical writing system of the ancient Gumei civilization had a total of $13$ symbols, which correspond one-to-one to the $13$ digits and symbols $0,1,2,3,4,5,6,7,8,9,+,*,=$ (called modern operators). For convenience, we use $13$ lowercase English letters $a,b,\ldots,m$ to represent these symbols (called Gumei operators). However, nobody knows the exact correspondence between the Gumei operators and the modern operators. On a stone wall, archaeologists found a set of equations written using Gumei operators. According to inference, each line contains exactly one equals sign, and the left and right sides of the equals sign are arithmetic expressions (containing only digits and symbols), and the computed results on both sides are equal. Assuming this set of equations is correct, write a program to decode the correspondence between Gumei operators and modern operators.

- The first line contains the number of equations $N$ ($1 \le N \le 1000$). The following $N$ lines each contain one equation. - The length of each equation is from $5$ characters to $11$ characters.

- If there is no correspondence that can satisfy this set of equations, output `noway`. - If there exists a correspondence that can satisfy this set of equations, output all correspondences between Gumei operators and modern operators that can be determined. Each line contains two characters: the first character is a Gumei operator, and the second character is the corresponding modern operator. Output them in lexicographical order.

**Sample Explanation** In the example above, possible corresponding modern expressions could be $\{6*2=12, 2=1+1\}$, $\{6*4=24, 4=2+2\}$, $\{6*8=48, 8=4+4\}$. It can be seen that the only correspondences that can be determined are: $a$ corresponds to $6$, $b$ corresponds to $*$, $d$ corresponds to $=$, and $f$ corresponds to $+$. These should be output. However, although ${c,e}$ can be matched with modern operators to make the equations valid, there is no unique correspondence, so they should not be output. The other Gumei operators ${g,h,\ldots,m}$ cannot be determined at all and also should not be output. Translated by ChatGPT 5