Sail Shreds - 8

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

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

삼각형 조각은 꼭짓점의 평면 좌표로 주어지고, 원래 돛은 정수 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를 나타내며, Ai는 (Ai,x, Ai,y), Bi는 (Bi,x, Bi,y), Ci는 (Ci,x, Ci,y)의 좌표를 가진다. 모든 좌표는 0 ≤ Ai,x, Ai,y, Bi,x, Bi,y, Ci,x, Ci,y ≤ 1 000 000을 만족한다.

입력에 주어진 삼각형의 위치는 문제가 되지 않는다. 예를 들어 세 번째 줄을 6 6 14 5 16 6으로 바꿔도 조각의 집합은 같다.

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