该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

描述一天早上，你起床的时候想：“我编程序这么牛，为什么不能靠这个赚点小钱呢？”因此你决定编写一个小游戏。

游戏在一个分割成$\red {w * h}$个正方格子的矩形板上进行。

如图所示，每个正方格子上可以有一张游戏卡片，当然也可以没有。

当下面的情况满足时，我们认为两个游戏卡片之间有一条路径相连：

路径只包含水平或者竖直的直线段。路径不能穿过别的游戏卡片。但是允许路径临时的离开矩形板。下面是一个例子：

这里在 $\red{(1, 3)}$和 $\red{(4, 4)}$处的游戏卡片是可以相连的。

而在 $\red{(2, 3)}$ 和 $\red{(3, 4)}$ 处的游戏卡是不相连的，因为连接他们的每条路径都必须要穿过别的游戏卡片。

你现在要在小游戏里面判断是否存在一条满足题意的路径能连接给定的两个游戏卡片。

输入格式

输入包括多组数据。一个矩形板对应一组数据。

每组数据包括的第一行包括两个整数$\red w$和$\red h$ ($\red{1 <= w, h <= 75)}$，分别表示矩形板的宽度和长度。

下面的$\red h$行，每行包括$\red w$个字符，表示矩形板上的游戏卡片分布情况。

使用‘$\red X$’表示这个地方有一个游戏卡片；使用空格表示这个地方没有游戏卡片。

之后的若干行上每行上包括$\red 4$个整数$\red {x_1, y_1, x_2, y_2 (1 <= x_1, x_2 <= w, 1 <= y_1, y_2 <= h)}$。给出两个卡片在矩形板上的位置（注意：矩形板左上角的坐标是($\red {1, 1}$)）。输入保证这两个游戏卡片所处的位置是不相同的。

如果一行上有$\red 4$个$\red 0$，表示这组测试数据的结束。

如果一行上给出$\red {w = h = 0}$，那么表示所有的输入结束了。

输出格式

对每一个矩形板，输出一行“Board #n:”，这里$\red n$是输入数据的编号。

然后对每一组需要测试的游戏卡片输出一行。

这一行的开头是“Pair m: ”，这里m是测试卡片的编号（对每个矩形板，编号都从1开始）。

接下来，如果可以相连，找到连接这两个卡片的所有路径中包括线段数最少的路径，输出“k segments.”，这里$\red k$是找到的最优路径中包括的线段的数目；

如果不能相连，输出“impossible.”。

每组数据之后输出一个空行。

样例

输入样例

5 4
XXXXX
X   X
XXX X
 XXX 
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0
0 0

输出样例

Board #1:
Pair 1: 4 segments.
Pair 2: 3 segments.
Pair 3: impossible.

提示