A shoemaker has \(N\) orders from customers which he must satisfy. He can work on only one job in each day, and jobs usually take several days. For the \(i\)-th job, the integer \(T_i\) (\(1 \leq T_i \leq 1000\)) denotes the number of days it takes the shoemaker to finish the job.

But popularity has its price. For each day of delay before starting to work on the \(i\)-th job, the shoemaker has agreed to pay a fine of \(S_i\) (\(1 \leq S_i \leq 10.000\)) cents per day. Help the shoemaker by writing a program to find the sequence of jobs with minimum total fine.


The input begins with a single positive integer on a line by itself indicating the number of the test cases, followed by a blank line. There is also a blank line between two consecutive cases.

The first line of each case contains an integer reporting the number of jobs \(N\), where \(1 \leq N \leq 1.000\). The \(i\)-th subsequent line contains the completion time \(T_i\) and daily penalty \(S_i\) for the \(i\)-th job.


For each test case, your program should print the sequence of jobs with minimal fine. Each job should be represented by its position in the input (the first job is at position 1). All integers should be placed on only one output line and each pair separated by one space. If multiple solutions are possible, print the first one in lexicographic order. The output of each test case should be separated from the next by a blank line.

Sample Input


3 4
1 1000
2 2
5 5

Sample Output

2 1 3 4

This is challenge 10026 of the ACM International Collegiate Programming Contest.

Upload Solution

Please log in to submit your solution.


Difficulty (6 votes)
Average test runtime 0.36
Points (changes over time) 10
Tried by 16 users
Solved by 12 users

Global ranking

# Name Runtime Points worth
1 Justin 0.14 17
2 mascent 0.15 16
3 Chris Danger 0.17 14
4 Pascal 0.18 13
5 Jan 0.20 12
6 ,s/java/NaN/gi 0.20 12
7 贝尔恩德 0.23 10
8 Nis 0.33 7
9 The Prof 0.34 7
10 JB 0.47 5
11 Mac 0.87 3
12 Dark 1.02 2