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 (1 ≤ n ≤ 1000), after which n lines contain the values of
Ti (1 ≤
Ti ≤ 1000) and
Si (1 ≤
Si ≤ 10000).
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.
4 3 4 1 1000 2 2 5 5
2 1 3 4