돛 조각 맞추기

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

각 조각은 삼각형이다. 돛에 그려진 줄무늬로 각 삼각형의 올바른 방향을 알 수 있다. 조각은 이 방향을 유지해야 한다. 그렇지 않으면 돛이 바람을 덜 견디고 다시 찢어질 수 있다. 조각은 회전하지 않고 옮길 수 있다.

다음 조건을 만족하도록 조각을 옮겨라.

• 직사각형 영역 전체를 덮는다.
• 두 삼각형이 교차하지 않는다. 즉, 서로 다른 두 삼각형의 내부에 공통으로 속하는 점이 없다.
• 어떤 삼각형도 일부라도 직사각형 밖으로 나가지 않는다.

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

첫 줄에 공백으로 구분된 세 정수 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번째 줄에는 공백으로 구분된 두 정수 A*i,x와 A*i,y를 출력한다. 이는 i번째 조각을 옮긴 뒤 점 Ai의 좌표이다.

돛의 왼쪽 아래 모서리는 (0, 0), 오른쪽 위 모서리는 (X, Y)이다.