A. Black Friday
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

After buying a monitor and a suitcase, then breaking the monitor by putting it in the suitcase on a flight, Leo resolved to make better personal finance decisions. However, he was challenged in this resolve when Black Friday came to pass. He ended up adding too many things to his shopping cart, to the dismay of his bank account. When all seemed lost, Leo remembered something. He had a coupon book lying around that he could use. These coupons were special and worked by first lowering his current shopping cart balance by $$$a_i$$$, and then giving a $$$d_i\%$$$ discount (removing $$$d_i\%$$$ of the adjusted balance). Due to a software error, Leo found that he could apply multiple coupons to the same shopping cart, and that applying all of the coupons in different orders could result in different final balances. Help Leo determine an optimal way to order the coupons that minimizes the final balance.

Input

The first line of input will consist of a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the number of coupons Leo has.

The following $$$n$$$ lines will consist of two real numbers $$$a_i$$$ and $$$d_i$$$ $$$(0.0 \le a_i \le 10^9, 0.0 \le d_i \lt 100.0)$$$ — the amount to reduce the price by and the discount percentage of the $$$i$$$-th coupon.

Both values $$$a_i,d_i$$$ will be printed to two decimal places. Also assume that Leo's shopping cart balance is large enough that it will never go negative after applying all of the coupons in any order.

Output

Output a line containing a permutation $$$c$$$ of the numbers from $$$1$$$ to $$$n$$$ — the order that the coupons should be applied in. $$$c_1$$$ should correspond to the first coupon used, $$$c_2$$$ should correspond to the second coupon used, and so on. $$$c$$$ should have $$$n$$$ elements and be separated by spaces. There may be multiple optimal orderings, and any optimal ordering will be accepted.

Examples
Input
2
16.65 0.00
0.00 16.65
Output
2 1
Input
3
200.00 10.00
10.00 20.00
50.00 5.00
Output
2 3 1