问题陈述
给定一系列 N 成对不同的不可约分数 \displaystyle \left(\frac{A_1}{B_1}, \frac{A_2}{B_2}, \dots, \frac{A_N}{B_N}\right),按升序排序。
约束
- 1 \leq N \leq 10^3
- 1 \leq A_i \leq 10^{18}
- 1 \leq B_i \leq 10^{18}
- \gcd(A_i, B_i) = 1
- (A_i,B_i) \neq (A_j,B_j) if i \neq j.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
输出
如果结果序列是 \displaystyle \left(\frac{C_1}{D_1}, \frac{C_2}{D_2}, \dots, \frac{C_N}{D_N} \right),按以下格式打印。
C_1 D_1 C_2 D_2 \vdots C_N D_N
示例输入 1
3 2 3 1 2 3 5
示例输出 1
1 2 3 5 2 3
自从 \displaystyle \frac{1}{2} \lt \frac{3}{5} \lt \frac{2}{3},排序后的序列为 \displaystyle \left(\frac{1}{2}, \frac{3}{5}, \frac{2}{3} \right).
示例输入 2
5 1 5 1 7 6 5 9 8 9 4
示例输出 2
1 7 1 5 9 8 6 5 9 4
示例输入 3
10 39 83 93 70 5 92 81 67 30 53 57 5 91 58 21 85 81 34 37 38
示例输出 3
5 92 21 85 39 83 30 53 37 38 81 67 93 70 91 58 81 34 57 5