부수적 피해 정리

헐크와 어보미네이션이 맨해튼의 빌딩 사이로 서로를 내던지며 벌인 대격돌을 기억하는가? 아니면 그린 고블린이 가엾은 스파이더맨을 벽돌 벽 여섯 장 너머로 처박아 버린 장면은? 그 벽들은 틀림없이 산산조각이 나 버렸을 것이다!

악당을 응징하는 슈퍼히어로가 있다는 것은 좋은 일이지만, 그들이 떠난 뒤 남겨진 부수적 피해를 누가 복구하는지 생각해 본 적이 있는가? 액션 정리 관리(ACM) 회사의 사장인 당신의 임무가 바로 그것이다. 큰 싸움이 끝나면 당신은 부서진 벽 조각을 모두 모아, 전투가 시작되기 전과 똑같이 다시 맞춰 놓아야 한다.

벽은 완벽한 직사각형 영역으로, 악당이 뚫고 지나가면 완벽한 삼각형 조각들로 부서진다. 정밀한 영상 분석을 통해 당신은 각 조각이 원래 벽의 어느 위치에서 나왔는지 정확히 알아냈다. 즉, 완성된 벽의 설계도를 손에 쥐고 있는 셈이다. 또한 두 조각이 맞닿는 곳에서는 항상 두 조각을 가르는 절단면(변)의 전체 길이를 따라 맞닿는다.

당신에게는 벽을 제자리에서 재조립하는 조립 로봇이 있다. 그러나 이 로봇은 한 번에 한 조각씩, 위에서 똑바로 아래로만 내릴 수 있다. 조각을 옆으로 밀거나 어떤 식으로든 회전시킬 수는 없다. 따라서 이미 놓인 조각이 나중에 내리는 조각의 진입을 막지 않도록, 조각을 내리는 순서를 신중히 정해야 한다. 로봇이 벽을 완전히 재조립할 수 있는 조각 순서를 구하라.

첫 번째 줄에는 재조립해야 할 벽의 개수 $W$가 주어진다. 각 벽은 다음과 같이 주어진다. 벽의 첫 줄에는 그 벽이 부서져 나온 삼각형 조각의 개수 $n$이 주어진다 ($2 \le n \le 1{,}000{,}000$). 이어서 $n$개의 줄이 주어지며, $i$번째 줄은 $i$번 조각을 여섯 개의 정수 $x_1\ y_1\ x_2\ y_2\ x_3\ y_3$으로 나타낸다. 이는 그 조각이 원래 벽에서 차지하던 삼각형 세 꼭짓점의 직교좌표이다. 세 꼭짓점은 항상 반시계 방향 순서로 주어지며, 넓이가 0이 아닌 삼각형을 이룬다. 모든 좌표는 $0$ 이상 $10^9$ 이하의 정수이고, 양의 $y$ 방향이 위쪽이다. $n$개의 조각은 빈틈이나 겹침 없이 하나의 직사각형 영역을 정확히 덮는다.

각 벽에 대해, 로봇이 각 조각을 똑바로 아래로 내려 벽을 재조립할 수 있는 조각 번호 순서를 한 줄에 출력한다.

여러 개의 유효한 순서가 존재할 수 있다. 답을 유일하게 만들기 위해, 그러한 순서들 중 사전순으로 가장 작은 것을 출력한다. 즉, 유효한 모든 순서를 앞에서부터 위치별로 비교했을 때 가장 작은 것을 고른다(가능한 한 가장 작은 첫 번째 조각으로 시작하고, 같으면 가능한 한 가장 작은 두 번째 조각을 택하는 식이다). $n$개의 번호를 공백 하나로 구분하여 출력한다.