Зимняя школа Харьков 2014, День 1 - Евгения Капуна (High)

Dura Lex

Time limit 1 second
Memory limit 256 MiB

Alex loves to order gadgets from abroad. Unfortunately for Alex, new customs regulations have been recently introduced, and according to them, he needs N passes to receive each gadget. Every pass is hard to get — to get i-th pass, Alex needs to spend D[i] days in a queue, and he can only stand in a queue for requesting not more than one pass at any moment. The most annoying part is i-th pass, the request can be denied with probability P[i]%, absolutely randomly, and moreover, if one pass request is denied, all the others get annulled automatically and Alex has to start it all over again. There is only one good thing about it - Alex can get passes in whatever order he wants.

Alex wants to get a new gadget by all means. He will try to get all the passes until he has them all. Help him select the order of requesting the passes so that the average time needed to collect them all will be minimum.

Input data

The first line of the input file contains an integer N.

Next, N lines contain two integers each: D[i] and P[i].

1 <= N <=10^5

0 <= D[i] <=1000

0 <= P[i] <= 100

Output data

Print N integers from 1 to N - desired order. If there are several optimal orders, print the lexicographically minimal.


Input example #1
1 10
10 10
5 90
Output example #1
3 1 2
Author Евгений Капун
Source Зимняя школа по программированию 2014, Харьков