题目描述

给定长度为 $N$ 的整数序列 $A=(A_1,A_2,\dots,A_N)$ 与 $B=(B_1,B_2,\dots,B_N)$。 考虑满足以下条件的长度为 $N$ 的有理数序列 $c=(c_1,c_2,\dots,c_N)$ 与 $d=(d_1,d_2,\dots,d_N)$。

• 对所有的 $1 \le i,j \le N$，都有 $(A_i+c_i)(B_j+d_j)=(A_j+c_j)(B_i+d_i)$。

请求出 $\displaystyle \sum_{i=1}^{N} \left ( |c_i|+|d_i| \right )$ 的最小可能值。

可以证明，本题的答案一定可以唯一地表示为分母为正、分子非负的最简分数 $p/q$。请输出 $p$ 与 $q$。

输入格式

输入按以下格式从标准输入读入：

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

输出格式

当本题的答案表示为分母为正、分子非负的最简分数 $p/q$ 时，请按以下格式输出：

• $p$ $q$

3
4 1 -8
3 1 -6

1 4

例如，可以取 $c=(0,0,0),d=(0,-\frac{1}{4},0)$，此时 $\sum_{i=1}^{N} \left ( |c_i|+|d_i| \right ) = \frac{1}{4}$。 并且，$\sum_{i=1}^{N} \left ( |c_i|+|d_i| \right )$ 不可能比它更小。

2
2 2
3 3

0 1

若答案为 $0$，则它表示为 $0/1$，因此输出 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

数据范围

• 所有输入值均为整数。

• $2 \le N \le 2 \times 10^5$

• $|A_i|, |B_i| \le 10^6$

• 来源：AtCoder ABC 479 G

子任务设置

• 子任务 1（30 分）：$N \le 2000$。
• 子任务 2（30 分）：$N \le 50000$。
• 子任务 3（40 分）：无特殊限制。