SP3406 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 _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_ >= 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.

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 "=".

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