A True Expression

Interview

Time limit2sMemory limit1024 MB

Summary

Given an expression A ? B = C with up to 1000-digit integers, list every base from 2 to 10 in which the equation holds.

Level: Easy3 of 10
Topics: Brute force, Implementation, Math
Solved: No attempts yet

문제

Many statements look false at first glance. For example, $2 + 2 = 11$ looks wrong, but in base $3$ the equation becomes true: $2_3+2_3=11_3=4_{10}$ .

You are given an expression $A ? B = C$ , where $A$ , $B$ , and $C$ are non-negative integers, and $?$ is one of the symbols for addition, subtraction, or multiplication. List every base from $2$ to $10$ in which the equation is true. Recall that base $n$ uses only the digits $0$ to $n-1$ .

입력

The input is one line containing the expression $A ? B = C$ . The symbol $?$ is one of $+$ , $-$ , or $*$ . The parts of the expression are separated by single spaces. Each of $A$ , $B$ , and $C$ has at most 1000 digits. Every number consists of the digits 0 to 9 and has no redundant leading zeros.

출력

Print the number $k$ of suitable bases on the first line. On the second line, print the $k$ bases in increasing order.

Examples3

Example 1
Input
```
2 + 2 = 11
```
Expected output
```
1
3
```
Example 2
Input
```
2 + 2 = 4
```
Expected output
```
6
5 6 7 8 9 10
```
Example 3
Input
```
2 * 2 = 5
```
Expected output
```
0
```