왕국 분할

카리 왕국이 무너지고 다른 왕국 $n$개가 그 영토를 나눈다. 왕국마다 값지게 여기는 땅이 다르다. 나파지는 정착할 너른 벌판을 원하고, 아시레마는 유전에만 관심이 있다.

각 왕국은 원하는 땅을 서로 겹치지 않는 원의 합집합으로 표시한다. 왕국 $i$는 받은 땅이 자신이 표시한 넓이의 $1/n$ 이상을 담으면 만족한다.

의회는 $y$축에 평행한 직선 $n-1$개로 카리를 자른다. 땅은 세로 띠 $n$개로 나뉘고, 띠 하나는 왕국 하나에 돌아간다. 의회는 다음 규칙에 따라 왼쪽에서 오른쪽으로 선을 긋는다.

마지막으로 그은 선의 위치를 $x$라 하고, 첫 선을 긋기 전에는 $x$를 음의 무한대로 둔다. 아직 띠를 받지 못한 왕국 $i$마다, $x$와 $x_i$ 사이의 띠가 왕국 $i$가 표시한 넓이의 $1/n$ 이상을 담는 가장 작은 $x_i \ge x$를 잡는다. 의회는 $x_i$가 가장 작은 왕국에 그 띠를 주고 $x_i$에 선을 그은 다음, 남은 왕국을 두고 같은 과정을 반복한다. 끝까지 남은 왕국은 마지막 선의 오른쪽을 모두 가진다.

$x_i$가 가장 작은 왕국이 여럿이면 번호가 작은 왕국이 먼저 받는다. 차이가 $10^{-9}$보다 작은 두 위치는 같은 위치로 본다.

이 규칙은 언제나 왕국 $n$개에 모두 띠를 나눠 주고, 모든 왕국이 만족한다. 왕국이 띠를 받는 순서를 출력한다.

첫째 줄에 카리를 나누는 왕국의 수 $n$ ($1 \le n \le 30$)이 주어진다. 이어서 왕국 번호 순서대로 구역 $n$개가 주어진다.

$i$번째 구역의 첫째 줄에는 왕국 $i$가 표시한 원의 개수 $m_i$ ($1 \le m_i \le 30$)가 주어진다. 다음 $m_i$개 줄에는 원 하나의 중심 좌표와 반지름을 나타내는 정수 $x$, $y$, $r$ ($-1000 \le x, y \le 1000$; $1 \le r \le 1000$)가 주어진다. 한 구역 안의 원은 서로 겹치지 않지만 접할 수는 있다. 서로 다른 왕국이 표시한 원은 어떻게 겹쳐도 된다.

한 줄에 정수 $n$개를 공백으로 구분해 출력한다. 왼쪽부터 차례로 띠를 받는 왕국의 번호이다.

그림은 첫 번째 입력에서 각 왕국이 표시한 원이다. 왕국 1은 1'과 1''이라고 적힌 원 두 개를, 왕국 2와 왕국 3은 모두 2와 3이라고 적힌 가운데 원을 골랐다. 점선은 땅을 공평하게 나누는 한 가지 방법이지만 의회가 긋는 선은 아니다. 의회는 $y$축에 평행한 직선만 쓴다.

왕국 1이 표시한 넓이는 $8\pi$이고, 필요한 $8\pi/3$은 왼쪽 원 안 $x \approx 0.5299$에서 채워진다. 왕국 2와 왕국 3이 표시한 넓이는 각각 $4\pi$이고, 필요한 $4\pi/3$은 $x \approx 3.4701$에서 채워진다. 그래서 첫 띠는 왕국 1이 받는다. 이어서 왕국 2와 왕국 3의 위치가 같으므로 번호가 작은 왕국 2가 먼저 받고, 왕국 3은 두 번째 선의 오른쪽 전부, 곧 자기 원의 3분의 2를 받는다.