High School Programming League Problems Archive

Little Johny decided to play at a chemist. He found his "Little Chemist" kit, placed all his test tubes on his parents' favorite carpet, and filled them with various chemicals. But while he was pondering on what he really wanted to do, his dog joined the game and knocked over all the tubes! The parents are going to be mad, since all the chemicals will leave nasty marks on the carpet, and so Johny is desperately trying to minimize the damage. All the test tubes are of different sizes, and from each of them their content is spilling out at different rate (i.e. the puddles on the floor are growing at different speeds). The test tubes contain different chemicals, so each puddle will make the carpet dirty to a different degree. The only thing Johny can do is to try to soak up the puddles on the floor into a mop (however, stains after each puddle will remain on the carpet). There arises a problem - in what order to deal with the chemicals (while Johnny is fighting with one of them, the others continue to spill), so as to minimize the mess. The problem is too hard for Johnny, so he has asked his elder sister/brother (that is, You) for help.

The problem

There are given n test tubes. From each of them some chemical is spilling out at the rate given by w_i (the size of i-th puddle is given by the following function of time: r_i = w_it) and the chemical in it has "staining factor" b_i. All test tubes have enough content to continue spilling during all the time Johny needs to clean the mess. Because Johny has wasted the first moment on calming down and planning his actions, you can assume he begins the cleaning at the moment t₀ = 1. Each puddle has to be wiped. The time needed to wipe the i-th puddle is given by w_it (that is, the size of the puddle), where t is the moment when Johnny begins wiping, since you can assume that at this moment Johnny collects the test tube, and the content stops spilling out. After dealing with one puddle Johny immediately begins to wipe the next one (so the wiping of the (i+1)-st puddle begins at the moment t+w_it). The overall mess will be proportional to the size of each stain and its "staining factor": A = Σ _j=1,..,n b_jr_j, where b_j i r_j are the properties of the puddle wiped as the j-th in order. The goal is to find an order of wiping which minimizes A.

Input

The first line of input will contain an integer m - the number of test cases. Each test case consists of integer n, specifying the number of test tubes, and n pairs of floating-point numbers w_i b_i (these are the properties of each puddle), i = 1, ..., n, 1 ≤ m ≤ 100, 2 ≤ n ≤ 50000, 0 < w_i ≤ 1000, 0 < b_i ≤ 1000.

Output

For each test, n integers (separated by single spaces) should be written. These numbers describe the wiping order - number k on the i-th position means that the k-th puddle from input should be wiped as the i-th in order. In case of "draws" (when the order of two consecutive puddles is not important, i.e. swapping them does not affect the value of A) the one which appeared earlier in the input data should be written first. At the end of each test, one new-line character should be written.

Example

Input:
2
2
1 10
0.1 1
3
0.1 1
0.5 5
1.0 10

Output:
1 2
3 2 1

Scoring

By solving this problem you score 10 points.