Description

You are given a sequence $a_i(i\in[1,n])$ of positive rational numbers of length $n$, we define an operation as:

Choose an index $j$, then $\forall i\in[1,n]$, let $a_i\gets\frac{a_i}{a_j}$.

Find out the minimum value of the sequence after operations are carried out any number of times.

Input Format

The first line of the input contains a single positive integer $n$: the length of the sequence.

Then the next $n$ lines, line $i+1$ contains two space separated positive integers $x_i,y_i$, indicating that $a_i=\frac{x_i}{y_i}$.

Output Format

One line, two positive integers $x,y$, indicating that the minimum value is $\frac{x}{y}$.

Note that the fraction you output must be the simplest fraction. In particular, if the simplified result is an integer, $y$ is expected to be $1$.

5
4 3
22 8
3 99
4 3
17 43

4 363

Hint

Example Explanation

Carry out operations for $4$ times, selecting indices $5,4,1,2$. The minimum value is $\frac{4}{363}$, it can be proved that no smaller value exists.

Constraints

This problem uses bundled testing.

For all data, it is guaranteed that:

$2\le n\le 10^6$，$\forall i\in[1,n],0<x_i,y_i\le 10^9$.