B - Bases

Time limit: 3 s
Memory limit: 256 MiB
Languages: C, C++, Java, Haskell, ... (details)

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{“=”}$.

The input must be read from standard input.


For each test case in the input your program should produce a single line in the output, indicating for which bases the given equation holds.

If the expression is true for infinitely many bases, print $\texttt{“B+”}$, where $B$ is the first base for which the equation holds.

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{‘*’}$.

The output must be written to standard output.

Sample test(s)

6*9=42 10000+3*5*334=3*5000+10+0 2+2=3 2+2=4 0*0=0 =
13 6 10 * 5+ 2+