Parentheses X93697

You are given N fractions:

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 ≥ 1. Each of the following N lines contains a description of one fraction: i+1-th line (1 ≤ i ≤ N) of each case contains two integers n_i and d_i, where |n_i|, |d_i| ≤ 10⁹, and n_i, d_i ≠ 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¹⁸.

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.