돛 조각 맞추기 - 5

최근 이틀 동안 몰아친 폭풍 때문에 선원 몇 명이 지중해의 무인도에 난파되었다. 무전기가 고장 나서 구조를 요청할 수 없고, 살아남을 유일한 길은 뗏목을 타고 탈출하는 것이다. 뗏목을 움직이려면 돛이 필요하다. 그들은 난파선에서 주돛을 건졌지만 여러 조각으로 찢어져 있다. 그래서 조각들을 꿰매어 원래 돛을 복원해야 한다.

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

각 삼각형 조각의 꼭짓점 좌표와 원래 돛의 크기가 주어진다. 돛은 가로 X, 세로 Y인 직사각형이다. 조각을 회전시키지 않고 옮겨서 원래 돛을 복원하라. 특히 다음 조건을 만족해야 한다.

• 직사각형 영역 전체를 덮는다.
• 두 조각이 겹치지 않는다. 즉 서로 다른 두 삼각형의 내부에 동시에 속하는 점이 없다.
• 일부라도 직사각형 밖에 놓이는 삼각형이 없다.

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

입력 파일은 하나의 테스트 케이스를 나타내며 다음 구조를 갖는다. 첫 줄에는 정수 N, X, Y가 공백으로 구분되어 주어진다. X와 Y(1 ≤ X, Y ≤ 1 000 000)는 원래 돛의 크기이며 X는 가로, Y는 세로이다. N(2 ≤ N ≤ 1 000)은 돛 조각의 개수이다.

다음 N개의 줄은 각 삼각형을 설명한다. (i + 1)번째 줄에는 여섯 정수 Ai,x, Ai,y, Bi,x, Bi,y, Ci,x, Ci,y가 공백으로 구분되어 주어지며, 이는 i번째 삼각형의 세 꼭짓점 Ai, Bi, Ci를 나타낸다. 꼭짓점 Ai의 좌표는 (Ai,x, Ai,y)이고, Bi는 (Bi,x, Bi,y), Ci는 (Ci,x, Ci,y)이다. 모든 좌표는 0 이상 1 000 000 이하라고 가정해도 된다.

입력에서 삼각형의 위치는 중요하지 않다. 예를 들어 입력 예시의 셋째 줄을 6 6 14 5 16 6으로 바꾸어도 주어진 삼각형 집합은 같다.

출력은 정확히 N줄이어야 하며, 세 조건을 모두 만족하는 조각들의 배치를 나타낸다. i번째 줄에는 공백으로 구분된 두 정수 $A'_{i,x}$와 $A'_{i,y}$를 출력한다. 이는 i번째 조각을 옮긴 뒤의 점 Ai의 좌표이다. 돛의 왼쪽 아래 모서리 좌표는 항상 (0, 0)이고, 오른쪽 위 모서리는 (X, Y)이다(그림 참고).