We have N fractions, which are represented by A/B

Sort the fractions in increasing order

In the case where two fractions are equivalent, output the fraction that appeared in the sequence first

The first line of input containes an integer, N, that denotes the number of fractions.

This is followed by N lines, containing 2 integers each. The i+1th line contains integers A_{i} and B_{i}

N lines, each containing 1 fraction, from smallest to largest

2≤N≤2e5

0≤A≤2e9

1≤B≤2e9

Subtask 1 (0%): Sample testcases

Subtask 2 (31%): No repeated fractions i.e. A_{i}/B_{i}≠A _{j}/B_{j} for all 1≤i,j≤N where i≠j

Subtask 3 (69%): No more constraints

5

4 5

2 3

1 3

8 2

2 6

1 3

2 6

2 3

4 5

8 2

Subtask | Score |
---|---|

1 | 0 |

2 | 31 |

3 | 69 |