픽셀 임대

해리엇 에멜은 자기 웹 페이지의 공간을 10픽셀 × 10픽셀짜리 블록 단위로 빌려준다. 페이지는 가로세로 10픽셀 간격의 격자선으로 나뉘어 있고, 누구든 이 격자의 블록을 빌려 그림이나 광고를 올릴 수 있다.

에멜은 손님 대부분이 직사각형 모양으로 블록을 고를 것이라고 예상했지만, 그렇지 않은 손님도 있었다. 어느 안경점은 안경 모양으로 블록을 골랐고, 활을 파는 가게는 과녁 모양으로 블록을 골랐다.

장부를 간단하게 관리하려고 에멜은 한 번의 신청이 반드시 하나의 직교 볼록(orthogonally convex) 블록 집합이어야 한다는 규칙을 세웠다. 직교 볼록이란 격자의 어느 행이든 어느 열이든 그 집합과 만나는 부분이 비어 있거나 연속된 한 덩어리라는 뜻이다.

손님이 원하는 블록을 아무렇게나 고르면, 에멜은 그 블록을 모두 포함하는 가장 작은 직교 볼록 영역을 계산해서 그 영역을 빌려준다. 이 영역을 구하는 프로그램을 작성하시오.

입력으로 주어지는 신청은 모두 이렇게 얻은 최소 영역이 하나로 이어져 있다. 즉 영역 안의 두 픽셀을 어떻게 고르더라도, 영역 안의 픽셀만 밟으면서 상하좌우로 움직여 한쪽에서 다른 쪽으로 갈 수 있다.

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

각 테스트 케이스의 첫 줄에 손님이 고른 블록의 개수 $n$ ($1 \le n \le 10000$)이 주어진다. 이어지는 한 줄 이상에 정수 $2n$개가 $r_0\ c_0\ r_1\ c_1 \dots r_{n-1}\ c_{n-1}$ 순서로 주어진다. $r_i$와 $c_i$는 $i$번째 블록의 왼쪽 위 픽셀의 행 번호와 열 번호다. 좌표는 모두 10의 배수이고 $0 \le r_i, c_i \le 10^9$이다. 한 테스트 케이스 안에서 같은 좌표 쌍이 두 번 나오지는 않는다.

각 테스트 케이스는 고른 블록을 모두 포함하는 최소 직교 볼록 영역이 하나로 이어진 다각형이 되도록 주어진다.

0 하나만 있는 줄을 만나면 입력이 끝난다.

테스트 케이스마다 한 줄씩 출력한다. 줄의 처음에 Case k: 를 출력한다. $k$는 1부터 세는 테스트 케이스 번호다. 그 뒤에 최소 직교 볼록 영역의 꼭짓점을 행 번호, 열 번호 순서로 모두 출력한다. 수는 공백 하나로 구분하고, 첫 꼭짓점을 마지막에 다시 적지 않는다.

첫 꼭짓점은 영역에서 행 번호가 가장 작고 그중 열 번호가 가장 작은 블록의 왼쪽 위 픽셀이다. 거기서 출발해 영역의 테두리를 시계 방향으로 한 바퀴 돈다. 위쪽 변에서는 오른쪽으로, 오른쪽 변에서는 아래로, 아래쪽 변에서는 왼쪽으로, 왼쪽 변에서는 위로 나아간다. 테두리는 영역에 속한 픽셀만 밟아 따라가고, 진행 방향이 꺾이는 픽셀마다 그 픽셀의 행 번호와 열 번호를 출력한다.