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 Di 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 probabilityPi%, 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

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

Next, N lines contain two integers each: Di and Pi.

1 <= N <= 105

0 <= Di <= 1000

0 <= Pi <= 100

Output

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