E - 分数のソート 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

問題文

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
  • i \neq j ならば (A_i,B_i) \neq (A_j,B_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

Problem Statement

Given a sequence of N pairwise-distinct irreducible fractions \displaystyle \left(\frac{A_1}{B_1}, \frac{A_2}{B_2}, \dots, \frac{A_N}{B_N}\right), sort it in ascending order.

Constraints

  • 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.
  • All input values are integers.

Input

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

If the resulting sequence is \displaystyle \left(\frac{C_1}{D_1}, \frac{C_2}{D_2}, \dots, \frac{C_N}{D_N} \right), print it in the following format.

C_1 D_1
C_2 D_2
\vdots
C_N D_N

Sample Input 1

3
2 3
1 2
3 5

Sample Output 1

1 2
3 5
2 3

Since \displaystyle \frac{1}{2} \lt \frac{3}{5} \lt \frac{2}{3}, the sorted sequence is \displaystyle \left(\frac{1}{2}, \frac{3}{5}, \frac{2}{3} \right).

Sample Input 2

5
1 5
1 7
6 5
9 8
9 4

Sample Output 2

1 7
1 5
9 8
6 5
9 4

Sample Input 3

10
39 83
93 70
5 92
81 67
30 53
57 5
91 58
21 85
81 34
37 38

Sample Output 3

5 92
21 85
39 83
30 53
37 38
81 67
93 70
91 58
81 34
57 5