돛 조각 - 2

최근 이틀 동안 폭풍이 몰아쳐 선원 무리가 지중해의 한 사막 섬에 난파되었다. 무전기가 고장 나서 도움을 요청할 수 없고, 살아남을 유일한 방법은 뗏목을 타고 탈출하는 것이다. 뗏목에는 돛이 필요하다. 난파선에서 주돛을 건졌지만 여러 조각으로 찢어져 있어서, 조각들을 꿰매 원래의 돛을 복원해야 한다.

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

각 삼각형은 꼭짓점의 평면 좌표로 주어진다. 원래 돛은 가로 X, 세로 Y인 직사각형이다. 조각을 회전하지 않고 평행 이동만 하여 다음 조건을 만족하도록 돛을 복원하라.

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

첫 줄에 세 정수 N, X, Y가 공백으로 구분되어 주어진다. X와 Y(1 ≤ X, Y ≤ 1 000 000)는 원래 돛의 가로와 세로이고, N(2 ≤ N ≤ 1 000)은 삼각형 조각의 개수이다.

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

조각이 입력에서 어디에 놓여 있는지는 중요하지 않다. 예를 들어 세 번째 줄을 6 6 14 5 16 6으로 바꿔도 조각 집합은 같다.

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