406832: GYM102566 I Fast Race

You have recently been hired as a software engineer by a new Auto Racing Company. Since you are new in this field, the company gave you one of their easiest tasks.

Basically, they got some races scheduled for the next week, with huge prizes, but also a lot of bets, and, therefore, they would like to find out some relevant information about the final scoreboard. Given that these races are in a straight line and each of them lasts for exactly $$$10^{18}$$$ minutes (the researchers proved that this is the exact moment of time when a person loses interest in what is going on), and you know for each car what is its speed and its starting position, you need to find out how the final scoreboards is going to look like, and what is the last moment of time when a change in the scoreboard happens.

The first line of the input will contain the number $$$R \leq 20$$$, representing the number of races.

The first line of each race will contain one positive integer: $$$N \leq 10^5$$$

The next $$$N$$$ lines of each race will contain two integers, $$$0 \leq P \leq 10^5$$$, the position of the current car, and $$$0 \leq S \leq 10^5$$$, the speed of the current car.

The company guarantees that there will not be two cars with the same characteristics (i.e. there is no pair of cars such that they have both, the same staring position and the same speed).

For each race, you should output two lines, first one containing $$$N$$$ integers, the indexes of the cars as they appear in the final scoreboard, second one containing one floating number, $$$T$$$, the time of the last change in the scoreboard, with a precision of $$$10^{-5}$$$.

1
10
1 20
0 20
5 6
7 6
3 9
2 10
3 14
18 18
30 30
0 0

9 1 2 8 7 6 5 4 3 10 
9.000000