게임

어느 날 아침, 잠에서 깨어 이렇게 생각합니다. "나는 정말 뛰어난 프로그래머야. 이 실력으로 돈을 좀 벌어보면 어떨까?" 그래서 컴퓨터 게임을 하나 만들기로 합니다.

게임은 가로 $w$칸, 세로 $h$칸으로 이루어진 직사각형 판 위에서 진행됩니다. 각 칸에는 게임 말이 놓여 있을 수도 있고, 놓여 있지 않을 수도 있습니다.

이 게임의 핵심은 두 게임 말을 다음 두 조건을 모두 만족하는 경로로 이을 수 있는지를 판단하는 것입니다.

1. 경로는 여러 개의 직선 구간으로 이루어지며, 각 구간은 수평 또는 수직 방향이다.
2. 경로는 다른 게임 말이 놓인 칸을 지나가지 않는다.

경로는 판 바깥으로 잠시 벗어나도 됩니다.

예를 들어, 두 말을 잇는 어떤 경로가 다른 말을 하나도 지나지 않으면 두 말은 연결할 수 있고, 어떤 경로를 그리더라도 반드시 다른 말을 지나야 한다면 두 말은 연결할 수 없습니다.

여러분이 만들어야 할 부분은 위 규칙에 따라 두 게임 말을 연결할 수 있는지, 그리고 연결할 수 있다면 필요한 직선 구간의 최소 개수가 몇 개인지를 판정하는 것입니다.

입력은 서로 다른 여러 게임 상황에 대한 설명으로 이루어져 있습니다.

각 게임 상황의 첫 줄에는 두 정수 $w$와 $h$ ($1 \le w, h \le 75$)가 주어지며, 각각 판의 가로와 세로 크기입니다. 이어지는 $h$개의 줄은 판의 내용을 나타내며, 각 줄은 정확히 $w$개의 문자로 이루어집니다. 해당 칸에 게임 말이 있으면 문자 X, 없으면 공백 문자입니다.

판의 설명 다음에는 네 정수 $x_1, y_1, x_2, y_2$ ($1 \le x_1, x_2 \le w$, $1 \le y_1, y_2 \le h$)로 이루어진 줄이 여러 개 이어집니다. 이는 두 게임 말의 좌표이며, 왼쪽 위 모서리의 좌표가 $(1, 1)$입니다. 주어지는 두 게임 말은 항상 서로 다르고, 두 칸에는 모두 게임 말이 놓여 있습니다. 한 판에 대한 게임 말 쌍의 목록은 0 0 0 0으로만 이루어진 줄로 끝납니다.

전체 입력은 $w = h = 0$인 게임 상황으로 끝나며, 이 상황은 처리하지 않습니다.

각 판마다 먼저 Board #n: 줄을 출력합니다. 여기서 $n$은 판의 번호입니다(1부터 시작). 그런 다음 그 판에 주어진 각 게임 말 쌍마다 한 줄씩 출력합니다. 각 줄은 Pair m: 로 시작하며, $m$은 그 판에서의 쌍 번호입니다(각 판마다 1부터 다시 셉니다). 이어서 두 말을 잇는 경로에 필요한 직선 구간의 최소 개수를 $k$라 할 때 k segments.를 출력하고, 위 규칙대로 연결할 수 없으면 impossible.을 출력합니다.

서로 이웃한 두 판의 출력 사이에는 빈 줄을 하나 넣습니다.