Problem F
What a Deal!

Emerald, Minecraft Wiki

While exploring the area around their new base, Kai discovered a village! Many of the villagers there are interested in trading their wares with her, but some of them trade the same goods! For example, both the village librarian and cartographer are interested in buying paper, while both the weaponsmith and toolsmith sell axes.

The villagers frequently have different buying and selling rates from each other. The cartographer is currently buying 24 paper for 1 emerald, while the librarian is buying 30 paper for 2 emeralds.

Kai wants to get the best deal for the resources that she has, so she has asked you to sort the trades of the same type in order of how beneficial they are to her. When two trades are equally beneficial, Kai prefers to trade in bulk because it takes less time.

Input

The first line of input is an integer, $n$, the number of available trades of a specific type. You are given that $2 \le n \le 1000$.

The next $n$ lines each each contain two integers, $g_i$ and $r_i$, indicating that for the $i$th trade, Kai can give $g_i$ of resource a to receive $r_i$ of resource b. You are given that $1 \le g_i, r_i \le 10^9$. Trade ratios are not necessarily unique.

Output

Output the $n$ trades in order of Kai’s preferences.

2
2 1
1 2

1 2
2 1

5
3 5
17 11
3 2
4 7
6 4

4 7
3 5
6 4
3 2
17 11

4
130515899 870000230
69486443 499291761
87161289 581004629
124603598 895333639

69486443 499291761
124603598 895333639
87161289 581004629
130515899 870000230