Kingdom Partitioning

The Kingdom of Qari has fallen, and $n$ other kingdoms are dividing its land. Each of them values a different part of Qari. Napaj wants open ground to settle on, while Acirema cares only about the oil fields.

Every kingdom marks the land it wants as a union of circles that do not overlap. Kingdom $i$ is content when the land it receives holds at least $1/n$ of the area it marked.

The council cuts Qari with $n-1$ vertical lines, that is, lines parallel to the $y$ axis. The lines split the land into $n$ strips, and each strip goes to one kingdom. The council draws the lines from left to right by the following rule.

Let $x$ be the position of the last line drawn, and let $x$ be at minus infinity before the first line. For every kingdom $i$ that holds no strip yet, take the smallest position $x_i \ge x$ such that the strip between $x$ and $x_i$ holds at least $1/n$ of the area kingdom $i$ marked. The council gives that strip to the kingdom with the smallest $x_i$, draws the line at $x_i$, and repeats with the remaining kingdoms. The kingdom left at the end takes everything to the right of the last line.

If several kingdoms share the smallest $x_i$, the kingdom with the smaller number is served first. Two positions that differ by less than $10^{-9}$ count as the same position.

This rule always serves all $n$ kingdoms, and every one of them ends up content. Print the order in which the kingdoms are served.

The first line contains an integer $n$ ($1 \le n \le 30$), the number of kingdoms dividing Qari. Then follow $n$ sections, one per kingdom, in the same order as the kingdom numbers.

The first line of the $i$-th section contains an integer $m_i$ ($1 \le m_i \le 30$), the number of circles marked by kingdom $i$. Each of the next $m_i$ lines contains three integers $x$, $y$ and $r$ ($-1000 \le x, y \le 1000$; $1 \le r \le 1000$), the coordinates of the center of one circle and its radius. Circles inside one section do not overlap, but they may touch. Circles marked by different kingdoms may overlap in any way.

Print $n$ integers on one line, separated by single spaces: the numbers of the kingdoms in the order they receive their strips, from left to right.

The picture shows the circles marked in the first example. Kingdom 1 marked the two circles labeled 1' and 1'', and kingdom 2 and kingdom 3 both marked the circle labeled 2 and 3. The dashed lines are one fair division of the land, but not the division the council draws here, because the council only uses lines parallel to the $y$ axis.

Kingdom 1 marked $8\pi$ in total and needs $8\pi/3$, which it reaches at $x \approx 0.5299$, inside its left circle. Kingdom 2 and kingdom 3 each marked $4\pi$ and need $4\pi/3$, which they reach at $x \approx 3.4701$. Kingdom 1 therefore takes the first strip. Kingdom 2 and kingdom 3 are then tied, so the smaller number goes first, and kingdom 3 keeps everything to the right of the second line, two thirds of its circle.