Boastin' Red Socks

Time limit1sMemory limit128 MB

Summary

Given a target probability p/q, find the red and black sock counts (total at most 50000) whose two-red draw probability equals p/q, minimizing total then reds.

Level: Hard8 of 10
Topics: Number theory, Math, Binary search, Brute force
Solved: No attempts yet

Problem

You have a drawer full of two kinds of socks: red and black. Altogether there are at least 2 and at most 50000 socks, but you do not know how many there are in total, nor how many are red or how many are black.

You have noticed, though, that when you reach into the drawer in complete darkness and pull out two socks at random, the probability that both of them are red is exactly $\frac{p}{q}$ , where $0 < q$ and $0 \le p \le q$ .

From this information alone, determine how many red socks and how many black socks are in the drawer. If several drawers are consistent with the probability, choose the one with the fewest socks in total; if there is still a tie, choose the one with the fewest red socks.

Input

The input consists of several test cases, one per line. Each line contains two integers $p$ and $q$ separated by a single space; both fit into a 64-bit unsigned integer. The input ends with a line containing two zeros, which must not be processed.

Output

For each test case, print one line containing the number of red socks and the number of black socks, separated by a single space. If no drawer with a total between 2 and 50000 socks matches the given probability, print impossible instead.

Examples3

Example 1

Input

1 2
6 8
12 2499550020
56 789
0 0

Expected output

3 1
7 1
4 49992
impossible

Example 2
Input
```
1 1
0 0
```
Expected output
```
2 0
```
Example 3
Input
```
1 3
0 0
```
Expected output
```
2 1
```