Collateral Cleanup

Remember the big fight where the Hulk and the Abomination threw each other through the buildings of Manhattan? Or the time the Green Goblin smashed poor Spider-Man through a good half-dozen brick walls? They must have shattered those walls into a million pieces!

It is great that we have superheroes to bring the villains to justice, but have you ever wondered who repairs all of the collateral damage once they are done? As president of the Action Cleanup Management (ACM) corporation, that is exactly your job. After a big fight you must take all of the broken pieces of a wall and put them back together just as they were before the battle began.

A wall is a perfectly rectangular region that shatters into perfectly triangular pieces when a villain is thrown through it. Through sophisticated visual analysis you have determined where in the original wall every little piece came from; in essence you hold a blueprint of the finished wall. Moreover, wherever two broken pieces meet, they meet along the full length of the break (edge) that separates them.

You have an assembly robot that reconstructs the wall in place. However, the robot can only lower each piece, one at a time, straight down from the top. It cannot move a piece from side to side or rotate it in any way. You must therefore be careful about the order in which the pieces are lowered, so that an already-placed piece never blocks a later piece from descending into its slot. Determine an order of the pieces that lets the robot fully reassemble the wall.

The first line contains an integer $W$, the number of walls to reassemble. Each wall is described as follows. The first line of a wall contains an integer $n$, the number of triangular pieces the wall was broken into ($2 \le n \le 1{,}000{,}000$). Then follow $n$ lines, the $i$-th of which describes piece $i$ with six integers $x_1\ y_1\ x_2\ y_2\ x_3\ y_3$: the Cartesian coordinates of the three corners of the triangle that piece occupies in the original wall. The three corners are always listed in counterclockwise order and form a triangle of non-zero area. All coordinates are integers between $0$ and $10^9$ inclusive, and the positive $y$ direction is the up direction. Together the $n$ pieces cover a rectangular region exactly, with no gaps and no overlaps.

For each wall, output on a single line the piece numbers in an order that lets the robot reassemble the wall by lowering each piece straight down.

Many orders may work. To make the answer unique, output the lexicographically smallest such order: among all valid orders, choose the one whose sequence of piece numbers is smallest when compared position by position (start with the smallest possible first piece; break ties by the smallest possible second piece, and so on). Print the $n$ numbers separated by single spaces.