돛 조각 - 1

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

각 조각은 삼각형이다. 돛에 있는 줄무늬 덕분에 각 삼각형의 올바른 방향을 쉽게 알아볼 수 있다. 방향은 반드시 지켜야 한다. 그렇지 않으면 돛이 바람을 제대로 견디지 못하고 다시 찢어질 수 있다. 선원들은 몇 시간 동안 원래 배치를 찾았지만 실패했다. 컴퓨터로 도와 달라고 부탁한다.

삼각형 조각들의 꼭짓점과 직사각형 돛의 크기가 주어진다. 조각을 회전시키지 않고 평행이동만 해서 돛을 복원하라. 배치는 다음 조건을 만족해야 한다.

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

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

첫 줄에 세 정수 N, X, Y가 공백으로 구분되어 주어진다. X는 돛의 가로 길이, Y는 세로 길이이며 $1 \le X, Y \le 1\,000\,000$을 만족한다. N은 조각의 개수이며 $2 \le N \le 1\,000$이다.

다음 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$이다. 모든 좌표는 $0 \le$ 좌표 $\le 1\,000\,000$을 만족한다.

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

정확히 N줄을 출력한다. i번째 줄에는 i번째 조각을 제자리로 옮긴 뒤의 점 $A_i$ 좌표 $A^*_{i,x}$와 $A^*_{i,y}$를 공백으로 구분해 출력한다. 돛의 왼쪽 아래 모서리는 (0, 0), 오른쪽 위 모서리는 (X, Y)이다.