Jigsaw

Interview

Time limit2sMemory limit512 MB

Summary

Given counts of corner, edge, and centre pieces, decide whether they form a complete w by h jigsaw and output any valid dimensions.

Level: Medium4 of 10
Topics: Math, Implementation, Brute force, Number theory
Solved: No attempts yet

Problem

You found an old jigsaw puzzle in the attic of your house, left behind by the previous occupants. Since you like puzzles, you decide to put it together. Before you start, though, you want to know whether this puzzle was left behind for a reason. Maybe it is incomplete? Maybe the box holds pieces from several puzzles?

If it looks like a complete puzzle, you also need to know how big your work surface must be. Nothing is worse than having to start a jigsaw over because you began on a small table.

The box does not tell you the dimensions $w \times h$ of the puzzle, but you can quickly count the three types of pieces in the box:

Corner pieces, which touch two edges of the puzzle.
Edge pieces, which touch one edge of the puzzle.
Centre pieces, which touch no edge of the puzzle.

Do these pieces add up to a complete jigsaw puzzle? If so, what was the original size of the puzzle?

Input

One line containing three integers $c$ , $e$ , and $m$ ( $0\leq c,e,m\leq10^9$ ): the number of corner pieces, edge pieces, and centre pieces, respectively.

Output

If there exist numbers $w$ and $h$ with $w\geq h\geq 2$ such that the original size of the jigsaw puzzle could have been $w\times h$ , output a single line containing $w$ and $h$ . Otherwise, output "impossible".

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

Examples4

Example 1
Input
```
4 8 4
```
Expected output
```
4 4
```
Example 2
Input
```
4 10 14
```
Expected output
```
impossible
```
Example 3
Input
```
4 12 6
```
Expected output
```
impossible
```
Example 4
Input
```
4 2048 195063
```
Expected output
```
773 255
```