Figure Out the Base

Time limit1sMemory limit128 MB

Summary

Given an equation with + and * over digit strings, find every base B >= 2 in which both sides evaluate to the same value.

Level: Medium7 of 10
Topics: Math, Brute force, Implementation, Number theory
Solved: No attempts yet

Problem

What is $6$ times $9$ ? The answer is $42$ . If you thought it was $54$ , take a short break before continuing — because $42$ is the result when the arithmetic is done in base $13$ .

For an integer $B \ge 2$ , every digit of a base- $B$ number is an integer between $0$ and $B-1$ . To read a base- $B$ number, multiply the rightmost digit by $1$ , the next digit to the left by $B$ , the next by $B^2$ , and so on, then add everything up.

Whether an equation is true can depend on the base being used. For example, $2+2=4$ is always true when $B \ge 5$ : base $4$ cannot use the digit $4$ , so $B$ must be at least $5$ . On the other hand, an equation such as $2+2=5$ can never be true in any base.

Given an equation, write a program that determines in which bases the equation is true.

Input

Each line of input is one test case of the form EXPR=EXPR. EXPR is an expression whose length does not exceed $17$ .

Every expression is always valid and consists only of +, *, and the digits 0 through 9. No expression starts with +, and no number has unnecessary leading zeros.

The last line of input contains a single =.

Output

For each test case, print the bases in which the given equation is true.

If infinitely many bases make the equation true, print B+, where $B$ is the smallest such base.

If the number of such bases is finite, print them in ascending order separated by spaces.

If no base makes the equation true, print *.

Examples4

Example 1

Input

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

Expected output

Example 2
Input
```
6*9=42
=
```
Expected output
```
13
```
Example 3
Input
```
2+2=4
=
```
Expected output
```
5+
```
Example 4
Input
```
0*0=0
=
```
Expected output
```
2+
```