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 A_i and B_i

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. A_i/B_i≠A _j/B_j 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