Matcom Online Grader

What do you get if you multiply $6$ by $9$? The answer, of course, is $42$, but only if you do the calculations in base $13$.

Given an integer $B \ge 2$, the base $B$ numbering system is a manner of writing integers using only digits between $0$ and $B - 1$, inclusive. In a number written in base $B$, the rightmost digit has its value multiplied by $1$, the second rightmost digit has its value multiplied by $B$, the third rightmost digit has its value multiplied by $B^2$ , and so on.

Some equations are true or false depending on the base they are considered in. The equation $2 + 2 = 4$, for instance, is true for any $B \ge 5$ — it does not hold in base $4$, for instance, since there is no digit $\texttt{‘4’}$ in base $4$. On the other hand, an equation like $2 + 2 = 5$ is never true.

Write a program that given an equation determines for which bases it holds.

Each line of the input contains a test case; each test case is an equation of the form $\texttt{“EXPR=EXPR”}$, where both $\texttt{“EXPR”}$ are arithmetic expressions with at most $17$ characters.

All expressions are valid, and contain only the characters $\texttt{‘+’}$, $\texttt{‘*’}$ and the digits from $\texttt{‘0’}$ to $\texttt{‘9’}$. No expressions contain leading plus signs, and no numbers in it have leading zeros.

The end of input is indicated by a line containing only $\texttt{“=”}$.

If the expression is valid only for a finite set of bases, print them in ascending order, separated by single spaces.

If the expression is not true in any base, print the character $\texttt{‘*’}$.