favorite We need a little bit of your help to keep things running, click on this banner to learn more

Shoemaker Problem

Shoemaker has n jobs (orders from customers) which he must make. Shoemaker can work on only one job in each day. For each i-th job, it is known the integer Ti, the time in days it takes the shoemaker to finish the job. For each day before finishing the i-th job, shoemaker must pay a fine of Si cents. Your task is to help the shoemaker, writing a program to find the sequence of jobs with minimal total fine.


Consists of multiple test cases. The first line of each test case contains the number of jobs n (1n1000), after which n lines contain the values of Ti (1Ti1000) and Si (1Si10000).


For each test case print in a separate line the sequence of jobs with minimal fine. If multiple solutions are possible, print the lexicographically first.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 4
1 1000
2 2
5 5
Output example #1
2 1 3 4