Problem E
Fixing Fractions
Following the patterns, we conclude that the following equation should also be true:
However, this is actually wrong in boring old standard maths. Therefore, we define a new kind of funky maths where it is allowed to cancel out digits on the left side of the equality sign. Cancelling a single digit works by removing one instance of your choice of that digit from both $a$ and $b$. This surely will make everyone’s life easier. Except yours, since you have to evaluate if two given fractions are equal in our 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 and 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.
Note that neither $a'$ nor $b'$ is allowed to contain leading zeroes after cancelling digits.
| Sample Input 1 | Sample Output 1 |
|---|---|
163 326 1 2 |
possible 1 2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
871 1261 13 39 |
possible 87 261 |
| Sample Input 3 | Sample Output 3 |
|---|---|
123 267 12339 23679 |
impossible |
