돛 조각 맞추기 - 7

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

각 조각은 삼각형이다. 돛에 있는 줄무늬 덕분에 각 삼각형의 올바른 방향은 쉽게 알 수 있다. 조각은 방향을 지켜야 한다. 방향을 잘못 꿰맨 돛은 바람을 덜 견디고 다시 찢어질 수 있기 때문이다. 선원들은 여러 시간 동안 원래 배치를 찾았지만 실패했고, 배치를 찾아 주는 프로그램을 요청했다.

각 삼각형은 세 꼭짓점의 평면 좌표로 주어진다. 원래 돛은 너비 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의 좌표다. 모든 좌표는 0 이상 1 000 000 이하이다.

입력에서 삼각형의 위치는 의미가 없다. 예를 들어 세 번째 줄을 6 6 14 5 16 6으로 바꿔도 같은 조각 집합이다.

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