돛 조각 맞추기 4

최근 이틀 동안 이어진 폭풍으로 선원 여러 명이 지중해의 한 무인도에 표류했다. 무전기가 고장 나서 도움을 요청할 수 없고, 살아남을 유일한 방법은 뗏목을 타고 탈출하는 것이다. 그런데 뗏목을 움직이려면 돛이 필요하다. 다행히 난파선에서 주돛을 건졌지만 돛은 여러 조각으로 찢어져 있다. 그래서 조각들을 꿰매어 원래의 돛을 되살려야 한다.

선원들은 각 조각이 삼각형이라는 것을 금방 알아챘다. 돛에 줄무늬가 있어서 삼각형 조각의 올바른 방향은 쉽게 알 수 있었다. 조각의 방향은 반드시 지켜야 한다. 그렇지 않으면 돛이 바람을 덜 견디고 다시 찢어질 수 있다. 선원들은 몇 시간 동안 원래 배치를 찾았지만 실패했다. 컴퓨터가 도울 수 있다고 생각해 당신에게 도움을 청했다.

주어지는 정보는 각 삼각형 조각 꼭짓점의 평면 좌표와, 직사각형이었던 원래 돛의 크기를 나타내는 두 정수 $X$와 $Y$이다. 과제는 조각을 회전시키지 않고 옮겨서 원래 돛을 복원하는 것이다. 이때 다음 조건을 만족해야 한다.

• 직사각형 영역 전체를 덮는다.
• 서로 다른 두 삼각형이 교차하지 않는다. 즉 두 삼각형의 내부에 동시에 속하는 점이 없다.
• 직사각형 밖으로 나가는 부분이 있는 삼각형이 없다.

각 입력에 대해 해가 존재한다고 가정해도 된다. 특히 조각들의 넓이 합은 원래 돛의 넓이와 같다. 같은 모양의 조각이 여러 개 있을 수 있다.

첫 줄에는 공백으로 구분된 세 정수 $N$, $X$, $Y$가 주어진다. $X$는 원래 돛의 너비, $Y$는 높이이며 $1 \le X, Y \le 1000000$을 만족한다. $N$은 조각의 개수이며 $2 \le N \le 1000$을 만족한다.

이어지는 $N$개의 줄은 삼각형을 나타낸다. $(i+1)$번째 줄에는 공백으로 구분된 여섯 정수 $A_{i,x}$, $A_{i,y}$, $B_{i,x}$, $B_{i,y}$, $C_{i,x}$, $C_{i,y}$가 주어진다. 이는 $i$번째 삼각형의 꼭짓점 $A_i$, $B_i$, $C_i$를 나타내며, $A_i$는 $(A_{i,x}, A_{i,y})$, $B_i$는 $(B_{i,x}, B_{i,y})$, $C_i$는 $(C_{i,x}, C_{i,y})$에 있다. 모든 좌표는 $0 \le$ 좌표 $\le 1000000$을 만족한다.

입력에서 삼각형이 놓인 위치는 중요하지 않다. 삼각형을 다른 위치로 평행이동해도 같은 조각 집합이다.

정확히 $N$개의 줄을 출력한다. $i$번째 줄에는 공백으로 구분된 두 정수 $A^*_{i,x}$와 $A^*_{i,y}$를 출력한다. 이는 $i$번째 조각을 제자리에 옮긴 뒤 점 $A_i$의 좌표이다. 문제의 세 조건을 모두 만족해야 한다. 돛의 왼쪽 아래 모서리는 항상 $(0, 0)$이고, 그림과 같이 오른쪽 위 모서리는 $(X, Y)$이다.