Chariot Race

Time limit2sMemory limit1024 MB

Summary

Split n coins into a bet on victory and the rest on defeat so Kratos profits in both outcomes, and list the splits with the largest winnings.

Level: Medium4 of 10
Topics: Math, Implementation
Solved: No attempts yet

Statement

One day fate brought Kratos to a chariot race, and he decided to test his luck by placing some coins on the outcome. He does not plan to waste money, so he resolved to bet only if he can come out ahead no matter how the race ends.

Kratos decides to bet $n$ coins. He puts some part $a$ on the victory of the charioteer he chose, and the rest on that charioteer's defeat. Only $x$ and $y$ are known at first: $x$ is the factor the bet is multiplied by if the charioteer wins, and $y$ is the factor if he loses. In addition, the player gets back the full amount of the part of the bet that was placed on the outcome that happened.

For example, if $a$ coins were bet on victory and the charioteer did win, Kratos receives $a + x \cdot a$ coins. If he lost, he receives $(n - a) + y \cdot (n - a)$ coins.

The warrior is not strong at math, so help him work out whether the coins can be split so that the amount he receives is strictly greater than the amount staked for every race result. He also wants to know the largest amount he can win in the best outcome. If a split is possible, he wants all such splits.

Input

The first line contains one integer $n$ , the number of coins ( $1 \le n \le 10^9$ ).

The second line contains two real numbers $x$ and $y$ , the win and loss coefficients of the charioteer ( $10^{-5} \le x, y \le 10^4$ , with at most 5 digits after the decimal point).

Output

If it is impossible to split the coins so that Kratos is guaranteed to come out ahead, print $-1$ on a single line.

Otherwise, print on the first line the maximum possible winnings in the best outcome as a real number. Its absolute or relative error must not exceed $10^{-6}$ . In the alternative outcome Kratos must still end up with a profit.

On the second line print $k$ , the number of splits that reach the maximum. Then print $k$ lines, each with two numbers $a$ and $b$ : the coins placed on victory and the coins placed on defeat. No split may repeat. Print the splits in increasing order of the amount placed on victory. It is guaranteed that the number of such splits is finite.

Examples2

Example 1
Input
```
6
1 2
```
Expected output
```
-1
```
Example 2
Input
```
8
3 1
```
Expected output
```
12.0000000
1
3 5
```