fractions

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

Input

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 Ai and Bi

Output

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

Limits

2≤N≤2e5

0≤A≤2e9

1≤B≤2e9

Subtasks

Subtask 1 (0%): Sample testcases

Subtask 2 (31%): No repeated fractions i.e. Ai/Bi≠A j/Bj for all 1≤i,j≤N where i≠j

Subtask 3 (69%): No more constraints

Sample Input

5
4 5
2 3
1 3
8 2
2 6

Sample Output

1 3
2 6
2 3
4 5
8 2


Submitting .cpp to 'fractions'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 1024MB
No. of ACs: 91
Your best score: 0
Source: Classic Problem (YeoBL20)

Subtask Score
1 0
2 31
3 69