Trivial bases

Time limit3sMemory limit2048 MB

Summary

Given A, B, and C as base-10 digit lists, find a base b below 10^19 where A times B equals C, or report impossible.

Level: Medium7 of 10
Topics: Math, Binary search, Implementation
Solved: No attempts yet

Problem

Mr. Trump recently won the US presidential election. Right after the vote, he called Mr. Malnar to check whether children across America can still take part in COCI, the international version of the Croatian Open Competition in Informatics.

The formal part of that call has not been made public. But the informal part leaked:

Mr. Malnar: So, what is new across the pond that nobody writes about in the news?

Mr. Trump: Nothing special. We recently made contact with aliens, but they are not too smart. If it comes to war, I am sure we will win.

Mr. Malnar: How do you know they are not too smart?

Mr. Trump: We intercepted the math homework of an alien elementary schooler. The kid wrote that $20 \cdot 2 = 100$ . Fine, the kid doesn't know better, but the teacher graded it as correct. I'm telling you, they are not smart. . .

Mr. Malnar: Don't those aliens have four tentacles in total on their hands?

Mr. Trump: Wow, man, how do you know that?

Mr. Malnar: Oh, Donald, you are the one who isn't smart. . .

Of course, Mr. Malnar immediately noticed that $20 \cdot 2 = 100$ is valid in base $4$ .

Your task is similar. For a given expression of the form $A \cdot B = C$ , find a base $b$ in which the expression is correct and which is strictly less than $10^{19}$ .

Input

The input consists of three lines. The first line gives the number $A$ , the second line gives $B$ , and the third line gives $C$ .

Each line consists of:

The number of digits $n$ ( $1 \le n \le 10^3$ ).
$n$ numbers $d_{n-1}, \dots, d_0$ ( $0 \le d_i \le 2^{30}$ , $d_{n-1} \ne 0$ ), the values of the digits of the number written in base $10$ . The most significant digit is $d_{n-1}$ , and the least significant digit is $d_0$ .

Output

Print a single line with a base $b$ ( $b < 10^{19}$ ) in which the expression holds. If no such base exists, print impossible. If several bases work, print any of them.

Hint

In base 13, the second sample works out as follows:

$(2 \cdot 13^0 + 1 \cdot 13^1 + 5 \cdot 13^2 ) \cdot (3 \cdot 13^0 + 11 \cdot 13^1 ) = 6 \cdot 13^0 + 12 \cdot 13^1 + 1 \cdot 13^2 + 5 \cdot 13^3 + 4 \cdot 13^4$

Examples3

Example 1
Input
```
2 2 0
1 2
3 1 0 0
```
Expected output
```
4
```
Example 2
Input
```
3 5 1 2
2 11 3
5 4 5 1 12 6
```
Expected output
```
13
```
Example 3
Input
```
2 3 2
2 3 2
3 10 12 4
```
Expected output
```
impossible
```