Cartesian Conquest

Time limit2sMemory limit512 MB

Summary

A rectangle N by M must be tiled by rectangles with side ratio 2:1, added one at a time so the union stays a rectangle; find the min and max tile counts.

Level: Hard8 of 10
Topics: Math, Number theory, Greedy, Implementation
Solved: No attempts yet

Problem

Long ago, in the land of Cartesia, the Rectangle Empire ruled. The empire was large and prosperous, and it grew by conquering its neighbors again and again. Most customs of that civilization are no longer understood, but the way it divided its land is known.

The territory of the empire was split into districts, and the districts always met three conditions.

Every piece of land the empire controls belongs to exactly one district.
On a map, the boundary of each district is a rectangle whose longer side is exactly twice its shorter side.
Both side lengths of a district are integers when measured in Ξ, the unit of length used in the Rectangle Empire.

When the empire was founded it consisted of a single district. After that it gained districts by conquest, and every time it took a new region it turned exactly that land into one new district. No two conquests happened at the same time. Adding a district was the only way the borders ever changed, and once a district existed it was never split, reshaped, or merged with another one.

The custom the empire cared about most is that the whole territory had to be a rectangle after every conquest. Unlike a single district, the whole territory does not need side lengths in the ratio $2:1$ .

Archaeologists found that at one moment the empire measured $N \times M$ in Ξ. Cartesia is an infinite plane, so these numbers can be very large. Over all the ways the empire could have been founded and expanded, find the minimum and the maximum possible number of districts at that moment.

Input

The first and only line contains two integers $N$ and $M$ ( $1 \le N, M \le 10^8$ ).

Output

Print the minimum number of districts and the maximum number of districts on one line, separated by a space. If no history of founding and conquest produces an $N \times M$ empire, print -1 -1 instead.

Note

The picture below shows how the minimum of 5 districts and the maximum of 8 districts are reached for a $10 \times 6$ empire. The labels #1, #2, #3, and so on give the order in which the districts were added, and the size of each district is written in brackets as $(k \times 2k)$ or $(2k \times k)$ .

Examples2

Example 1
Input
```
10 6
```
Expected output
```
5 8
```
Example 2
Input
```
1 1
```
Expected output
```
-1 -1
```