돛 조각 - 3

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

선원들은 곧 각 조각이 삼각형이라는 것을 알아챘다. 돛에 줄무늬가 있어서 삼각형 조각의 올바른 방향은 쉽게 식별할 수 있었다. 실제로 조각의 방향은 반드시 지켜야 한다. 그렇지 않으면 돛이 바람을 제대로 받지 못하고 다시 찢어질 수 있다. 선원들은 몇 시간 동안 원래 배치를 찾으려 했지만 성공하지 못했다. 컴퓨터가 도움을 줄 수 있다고 보고 당신에게 도움을 요청했다.

각 삼각형 조각의 꼭짓점 평면 좌표와, 직사각형이었던 원래 돛의 크기를 나타내는 두 정수 X, Y가 주어진다. 할 일은 조각을 회전시키지 않고 옮겨서 원래 돛을 복원하는 것이다(그림 참고). 구체적으로 삼각형은 다음 조건을 만족하도록 옮겨야 한다.

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

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

첫 줄에 정수 N, X, Y가 공백으로 구분되어 주어진다. X는 돛의 너비, Y는 돛의 높이이며 1 ≤ X, Y ≤ 1 000 000이다. N은 조각의 개수로 2 ≤ N ≤ 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의 좌표이며, A_i의 좌표는 (A_{i,x}, A_{i,y})이다. 모든 좌표는 0 이상 1 000 000 이하이다.

입력에서 삼각형의 위치는 의미가 없다. 모양만 사용된다.

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