Phone Hoseokman

Interview

Time limit1sMemory limit512 MB

Summary

Given the same number written in two unknown bases A and B, find the base-10 value X and the two bases, reporting Multiple or Impossible.

Level: Medium6 of 10
Topics: Math, Brute force, Implementation, String matching
Solved: No attempts yet

Problem

Phone Hoseokman is a master of base conversion. Since he can convert a number in any base to every other base, he decided to create a new problem. His problem proceeds as follows.

First, Phone Hoseokman chooses three numbers X, A, and B (0 ≤ X < 2^63, 2 ≤ A ≤ 36, 2 ≤ B ≤ 36, A ≠ B). Here X is in base 10. He then writes X in base A and X in base B on a piece of paper.

He then shows you the two numbers written on the paper. From the two given numbers, figure out the original number X, A, and B. If multiple combinations of (X, A, B) satisfy the conditions, print "Multiple"; if no combination is possible, print "Impossible".

Input

The first line gives X in base A and X in base B, separated by a space. Each digit is between 0 and z. The letters a through z mean 10 through 35.

Except for 0, each number does not start with 0, and its length is at most 70.

Output

If X, A, and B satisfying the problem's conditions exist uniquely, print X in base 10, A, and B separated by spaces. If there are two or more satisfying cases, print "Multiple"; if there are none, print "Impossible".

Constraints

0 ≤ X < 2^63
2 ≤ A ≤ 36
2 ≤ B ≤ 36
A ≠ B
X is 0 or a positive integer, and A and B are positive integers.

Hint

The value range of C++'s long long type and Java's Long type variable is at least -2^63 and less than 2^63.

Examples4

Example 1
Input
```
ep jh
```
Expected output
```
473 32 24
```
Example 2
Input
```
z z
```
Expected output
```
Impossible
```
Example 3
Input
```
0 0
```
Expected output
```
Multiple
```

Example 4

Input

2222222222222222222222222222222222222222222222222222222222222222222222 8888888888888888888888888888888

Expected output

Impossible