Problem Statement

We have $N$ balance beams numbered $1$ to $N$. The length of each beam is $1$ meters. Snuke walks on Beam $i$ at a speed of $1/A_i$ meters per second, and Ringo walks on Beam $i$ at a speed of $1/B_i$ meters per second.

Snuke and Ringo will play the following game:

• First, Snuke connects the $N$ beams in any order of his choice and makes a long beam of length $N$ meters.
• Then, Snuke starts at the left end of the long beam. At the same time, Ringo starts at a point chosen uniformly at random on the long beam. Both of them walk to the right end of the long beam.
• Snuke wins if and only if he catches up to Ringo before Ringo reaches the right end of the long beam. That is, Snuke wins if there is a moment when Snuke and Ringo stand at the same position, and Ringo wins otherwise.

Find the probability that Snuke wins when Snuke arranges the $N$ beams so that the probability of his winning is maximized.

This probability is a rational number, so we ask you to represent it as an irreducible fraction $P/Q$ (to represent $0$, use $P=0, Q=1$).

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq A_i,B_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the numerator and denominator of the irreducible fraction that represents the maximum probability of Snuke's winning.