송유관

록키 오일은 여러 개의 직사각형 유전을 소유하고 있으며, 각 유전에 새로운 유정(oil well)을 파고 있다. 각 유전에서는 모든 유정을 하나의 동서(E–W) 방향 송유관에 남북(N–S) 방향의 직선 파이프로 연결하려고 한다. 프로그램은 먼저 N–S 파이프들의 전체 길이가 최소가 되도록 E–W 송유관의 위치를 찾고, 가능하다면 유전의 지도를 그려야 한다.

각 유전은 E–W 방향으로 94, N–S 방향으로 73 크기의 격자이다. 좌표는 정수이며, 남서쪽 모서리가 $(1, 1)$, 북동쪽 모서리가 $(94, 73)$이다. 유정은 격자 안의 임의의 정수 좌표에 있을 수 있고, 서로 다른 유정은 서로 다른 위치에 있다. E–W 송유관은 어떤 정수 N–S 좌표에서 유전 전체를 가로지른다. E–W 좌표가 같은 유정들은 하나의 공통 N–S 파이프로 연결된다. 전체 길이가 최소가 되는 N–S 위치가 여러 개라면, 가장 남쪽(가장 작은 N–S 좌표)을 선택한다.

하나의 E–W 열에 대해, N–S 파이프는 E–W 송유관에서 그 열의 모든 유정까지 닿아야 하므로, 그 길이는 (송유관, 가장 낮은 유정) 중 더 낮은 값에서 (송유관, 가장 높은 유정) 중 더 높은 값까지의 거리이다. 전체 파이프 길이는 유정이 있는 모든 E–W 열에 대한 이 값들의 합이다.

예를 들어, 송유관을 N–S 좌표 11에 두면 E–W 위치 1의 유정은 송유관 위에 있어 길이가 0이고, E–W 위치 69의 두 유정은 길이 18의 파이프 하나를 공유하여 합이 18이다. 20에 두어도 18이며, 실제로 11부터 20까지 모든 위치가 최소이다. 이 중 가장 남쪽인 11을 선택한다.

지도를 그릴 수 있다면, 테두리와 라벨을 제외하고 69열, 19행 이내에 들어가야 한다. 지도에는 E–W 송유관, 모든 유정, 모든 N–S 파이프가 표시된다. 유정이 있는 부분만을, 네 변이 모두 5의 배수인 가장 작은 경계 직사각형으로 그린다. 모든 유정은 이 직사각형의 변 위가 아니라 내부에 있어야 한다. E–W 송유관은 항상 지도의 전체 너비를 가로지른다. 필요한 직사각형이 69열 또는 19행을 넘으면 그 유전은 그릴 수 없다.

입력은 하나 이상의 유전을 나타내며, 0 0만 있는 줄로 끝난다. 각 유전은 한 줄에 한 쌍씩, 유정의 E–W 좌표와 N–S 좌표를 나타내는 양의 정수 쌍 하나 이상으로 주어진다. -1 -1 줄은 한 유전의 데이터가 끝났음을 나타낸다.

각 유전에 대해 먼저 머리글 줄 OIL FIELD k를 출력한다. k는 1부터 시작하는 유전 번호이다.

지도를 그릴 수 있으면 지도를 그린다. 유정은 @, 파이프는 *, 빈 칸은 .로 나타낸다. 유정이 파이프보다 우선하므로, 유정과 파이프가 겹치는 칸에는 @를 출력한다. 그려진 영역 둘레에 테두리를 그리는데, N–S(세로) 변은 |, E–W(가로) 변은 -를 사용하되, 5의 배수인 모든 격자 위치(모서리 포함)에는 +를 놓는다. 각 +에는 유전에서의 좌표를 라벨로 붙인다. N–S +(행)의 라벨은 왼쪽 변의 + 바로 앞에 오른쪽 정렬로 붙이며, 가장 북쪽 행의 라벨은 그 줄의 맨 첫 칸에서 시작한다. E–W +(열)의 라벨은 아래쪽 테두리 바로 아래 줄에 쓰며, 가장 높은 자리 숫자가 + 바로 아래에 오도록 한다. 이 라벨들 때문에 일부 지도 줄은 앞쪽이 공백으로 시작한다.

지도를 그릴 수 없으면, 대신 Map is too big to draw for pipeline at p 한 줄을 출력한다. 여기서 p는 선택된 송유관의 N–S 좌표이다.