Fixing Fractions

Time limit1sMemory limit1024 MB

Summary

Given fractions a/b and c/d, decide whether removing the same digit positions from a and b can produce a fraction equal to c/d, and output the reduced pair if so.

Level: Medium5 of 10
Topics: String, Brute force, Math
Solved: No attempts yet

Problem

Maths is hard.[citation needed] But it could be easier! And the internet™ has found some excellent ways to make it easier. Take a look at the following true equations:

Following the patterns, we come to the conclusion that the following equation should also be true:

However, this is actually wrong in standard maths. So we define a new kind of funky maths where digits on the left side of the equality sign may be cancelled out. This will make everyone's life easier, except yours, because you have to decide whether two given fractions are equal in this new funky maths.

Input

The input consists of one line with four integers $a$ , $b$ , $c$ , and $d$ ( $1\leq a,b,c,d<10^{18}$ ), describing the two fractions $\frac{a}{b}$ and $\frac{c}{d}$ .

Output

If there exist integers $a'$ and $b'$ obtained from $a$ and $b$ by cancelling out the same digits, with $\frac{a'}{b'} = \frac{c}{d}$ in standard mathematics, output "possible", followed by $a'$ and $b'$ . Otherwise, output "impossible".

If there are multiple valid solutions, you may output any one of them.

Neither $a'$ nor $b'$ may contain leading zeroes after cancelling digits.

Examples3

Example 1
Input
```
163 326 1 2
```
Expected output
```
possible
1 2
```
Example 2
Input
```
871 1261 13 39
```
Expected output
```
possible
87 261
```
Example 3
Input
```
123 267 12339 23679
```
Expected output
```
impossible
```