SAMER08B - Bases

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 ≥ 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 B2, 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 ≥ 5 - it does not hold in base 4, for instance, since there is no digit '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.

Input

Each line of the input contains a test case; each test case is an equation of the form "EXPR=EXPR", where both "EXPR" are arithmetic expressions with at most 17 characters.

All expressions are valid, and contain only the characters '+', '*' and the digits from '0' to '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 "=".

Output

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 "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 '*'.

Example

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

Output:
13
6 10
*
5+
2+

Added by:Diego Satoba
Date:2008-11-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP JAVA PAS-GPC PAS-FPC
Resource:South American Regional Contests 2008

hide comments
2011-04-04 16:42:55 :D
No specific limit. It's limited only by other input restrictions. It could get pretty big, for example something like this: 9*9*9*9*9*9*9=10

Last edit: 2011-04-07 06:20:57
2010-05-12 14:03:22 numerix
What is the upper limit for the bases?

Edit: Great! I got an answer before a year has passed ...
Thanks!

Last edit: 2011-04-04 19:48:38
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.