Problem Statement

You are given length-$N$ integer sequences $A=(A_1,A_2,\dots,A_N)$ and $B=(B_1,B_2,\dots,B_N)$. Consider length-$N$ sequences of rational numbers $c=(c_1,c_2,\dots,c_N)$ and $d=(d_1,d_2,\dots,d_N)$ that satisfy the following condition.

• $(A_i+c_i)(B_j+d_j)=(A_j+c_j)(B_i+d_i)$ for all $1 \le i,j \le N$.

Find the minimum possible value of $\displaystyle \sum_{i=1}^{N} \left ( |c_i|+|d_i| \right )$.

It can be proved that the answer to this problem can be uniquely represented as an irreducible fraction $p/q$ with a positive denominator and a non-negative numerator. Output these $p$ and $q$.

Constraints

• All input values are integers.
• $2 \le N \le 2 \times 10^5$
• $|A_i|, |B_i| \le 10^6$

Input

The input is given from Standard Input in the following format:

• $N$
• $A_1$ $A_2$ $\ldots$ $A_N$
• $B_1$ $B_2$ $\ldots$ $B_N$

Output

When the answer to this problem is represented as an irreducible fraction $p/q$ with a positive denominator and a non-negative numerator, output it in the following format:

• $p$ $q$

3
4 1 -8
3 1 -6

1 4

For example, you can set $c=(0,0,0),d=(0,-\frac{1}{4},0)$, which achieves $\sum_{i=1}^{N} \left ( |c_i|+|d_i| \right ) = \frac{1}{4}$. Also, $\sum_{i=1}^{N} \left ( |c_i|+|d_i| \right )$ cannot be made smaller than this.

2
2 2
3 3

0 1

If the answer is $0$, it is represented as $0/1$, so output 0 1.

10
855263 -919070 120736 -779959 -789624 789495 -541451 139160 -406547 32421
-612084 -707431 843213 834659 -424146 549941 -799392 -553082 732456 357127

635454493436 120459

• Source: AtCoder ABC 479 G