Parentheses X93697

You are given $N$ fractions:

$$({n_1 \over d_1}) / ({n_2 \over d_2}) / ({n_3 \over d_3}) / \cdots / ({n_N \over d_N})$$

Assuming that you can execute the $N-1$ divisions in any way you want, your task is to find the smallest and largest result that can be obtained.

Input

Input consists of several cases. The first line of each case contains a single number $N \geq 1$. Each of the following $N$ lines contains a description of one fraction: $i+1$-th line ($1 \leq i \leq N$) of each case contains two integers $n_i$ and $d_i$, where $|n_i|, |d_i| \leq 10^9$, and $n_i, d_i \neq 0$. You can assume that the value of the product of all $M_i$, where $M_i = \max(|n_i|, |d_i|)$, does not exceed $10^{18}$.

Edit: Changed the limit to the one that was actually used.

The input ends with a single line containing 0.

Output

In the first line output $n_m$ and $d_m$ — the nominator and denominator of the smallest possible result. In the second line output $n_M$ and $d_M$ — the nominator and denominator of the largest possible result. Both should be given as irreducible fractions, with $d_m, d_M > 0$.