다각형 타일링

다각형 타일링 게임에서는 타일이라고 부르는 기본 도형만 써서 다각형 내부를 빈틈없이 채운다. 다각형 전체를 여러 조각으로 자르되 모든 조각의 모양이 주어진 타일 중 하나와 똑같아야 한다는 뜻이다. 여기서는 게임의 간단한 형태만 다룬다. 그림 7처럼 직사각형 타일이 두 종류 있고, 가로와 세로 크기는 각각 $1 \times 3$과 $3 \times 1$이다. 이 두 타일로 직교 다각형, 즉 모든 변이 수평이거나 수직인 다각형을 채운다. 그림 8(a)가 그런 다각형이고, 그림 8(b)는 $3 \times 1$ 타일 세 개와 $1 \times 3$ 타일 한 개로 그 다각형을 채운 모습이다.

그림 7: $1 \times 3$ 타일과 $3 \times 1$ 타일

좌표계는 다음 규칙을 따른다.

1. 다각형은 가장 아래 변이 x축 위에, 가장 왼쪽 변이 y축 위에 놓이도록 배치한다. 그림 8이 그 예다.
2. 다각형은 꼭짓점을 모두 나열한 순서 있는 점의 열로 나타낸다. 나열은 왼쪽 아래 꼭짓점, 즉 x축 위에 있는 꼭짓점 중 가장 왼쪽 것에서 시작해 반시계 방향으로 진행한다. 그림 8(a)의 다각형은 점의 열 [A, B, C, D, E, F, G, H]로 나타낸다.
3. 격자, 곧 가로와 세로가 모두 1인 정사각형은 오른쪽 위 꼭짓점의 x좌표와 y좌표를 묶은 쌍 $(x, y)$로 나타낸다. 그림 8(a)에는 각 격자의 좌표를 격자 안에 적어 두었다.
4. 타일은 세 수의 조 $(x, y, z)$로 나타낸다. $x$와 $y$는 그 타일이 덮는 격자 세 개 중 가운데 격자의 좌표이고, $z$는 방향이다. 타일이 가로면 $z = 0$, 세로면 $z = 1$이다. 그림 9에 예가 두 개 있다.

주어진 다각형을 채우는 방법을 찾는 프로그램을 작성한다. 다각형은 항상 채울 수 있다.

그림 8: 타일링의 예

그림 9: $(x, y, z)$ 표기의 예 두 가지

입력은 여러 개의 테스트 케이스로 이루어진다.

각 케이스는 채워야 할 다각형 하나를 나타낸다. 첫 줄에 다각형의 꼭짓점 개수 $N$ ($4 \le N < 100$)이 주어진다. 이어지는 $N$개의 줄에 위에서 정한 순서대로 꼭짓점을 한 줄에 하나씩 준다. 각 줄에는 x좌표와 y좌표를 공백 하나로 구분해 적는다.

다각형의 넓이는 항상 1000보다 작고, 모든 좌표는 100보다 작은 정수다.

0 하나만 있는 줄이 나오면 입력이 끝난다. 이 줄은 처리하지 않는다.

각 케이스마다 그 다각형을 채우는 타일 목록을 출력한다. 한 줄에 타일 하나를 x y z 형식으로, 세 수를 공백 하나로 구분해 쓴다.

타일링은 여러 가지가 나올 수 있으므로 다음 규칙이 정하는 하나만 출력한다. 다각형에 속한 격자를 $y$가 작은 순으로, $y$가 같으면 $x$가 작은 순으로 훑는다. 아직 어떤 타일도 덮지 않은 첫 격자를 $g$라고 하자. $g$를 덮는 타일은 $g$를 가장 왼쪽 격자로 하는 가로 타일이거나 $g$를 가장 아래 격자로 하는 세로 타일, 둘 중 하나뿐이다. 가로 타일을 먼저 놓아 보고, 그 선택으로는 다각형 전체를 채울 수 없으면 세로 타일을 놓는다. 남은 격자가 없을 때까지 이 과정을 되풀이한다. 이 규칙은 타일링을 하나로 결정한다.

출력하는 타일은 $y$가 작은 순으로, $y$가 같으면 $x$가 작은 순으로 정렬한다. 서로 다른 두 타일의 가운데 격자는 다르므로 이 정렬은 유일하다.

케이스와 케이스 사이에는 빈 줄을 하나 넣는다.