题目描述

我们有 $N$ 个编号为 $1$ 到 $N$ 的平衡梁。每根梁的长度是 $1$ 米。Snuke 在第 $i$ 根梁上以 $1/A_i$ 米/秒的速度行走，Ringo 在第 $i$ 根梁上以 $1/B_i$ 米/秒的速度行走。

Snuke 和 Ringo 将进行以下游戏：

• 首先，Snuke 以任意顺序连接这 $N$ 根梁，形成一根总长度为 $N$ 米的长梁。
• 然后，Snuke 从长梁的左端开始。与此同时，Ringo 在长梁上随机选择一个点作为起点。他们都向长梁的右端行走。
• 只有当 Snuke 在 Ringo 到达长梁的右端之前追上 Ringo 时，Snuke 才能获胜。也就是说，只有在某个时刻 Snuke 和 Ringo 在相同的位置时，Snuke 才能获胜；否则 Ringo 胜利。

如果 Snuke 安排这 $N$ 根梁以最大化获胜的概率，请找出 Snuke 获胜的概率。

这个概率是一个有理数，因此我们要求你将其表示为不可约分数 $P/Q$（若要表示 $0$，请使用 $P=0, Q=1$）。

约束条件

• $1 \leq N \leq 10^5$
• $1 \leq A_i, B_i \leq 10^9$
• 输入中的所有值均为整数。

输入

输入通过标准输入给出，格式如下：

$N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出

打印表示 Snuke 最大化获胜概率的不可约分数的分子和分母。

示例输入 1

2
3 2
1 2

示例输出 1

1 4

当从左到右按顺序连接梁 $2,1$ 时，Snuke 获胜的概率是 $1/4$，这是可能的最大值。

示例输入 2

4
1 5
4 7
2 1
8 4

示例输出 2

1 2

示例输入 3

3
4 1
5 2
6 3

示例输出 3

0 1

示例输入 4

10
866111664 178537096
705445072 318106937
472381277 579910117
353498483 865935868
383133839 231371336
378371075 681212831
304570952 16537461
955719384 267238505
844917655 218662351
550309930 62731178

示例输出 4

697461712 2899550585