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.

Input

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).

Output

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.