題目描述

给出一张n*m的地图，在地图上有一只虫子，样子很像龙，而且嘴能快速地喷（直射）出一种毒液，瞬间杀死敌人。

现在假设虫子的初始位置在 (x1,y1)，另外在 (x2,y2) 处有一个敌人。假设虫子移动一步需要一单位的时间，而杀死敌人不需要时间，且虫子的毒液射程无限远，但不能穿透障碍物。因为这是一只虫，所以它只可以向上、下、左、右四个方向移动。因为这是一只像龙的虫，所以它可以向上、下、左、右、左上、左下、右上、右下八个方向攻击

请问虫最少需要用多少时间才能消灭敌人。

輸入格式

第一行两个整数n,m，表示矩阵的规模 (n为高，m为宽)

接下来是n*m的矩阵，用O表示空地，X表示障碍物。

下面是若干行数据，每行为一对数据。每对数据包括4个整数，分别是表示敌人的坐标x2,y2,和虫的坐标x1,y1。

保证敌人和虫都不在障碍物上，最后用4个0表示输入结束。

輸出格式

一对数据输出一行。
如果一开始就能消灭敌人，时间为0: 如果无法消灭敌人，输出“Impossible!”。

Samples

3 4
OXXO
XXOO
XOOO
3 2 2 4
3 3 1 1
0 0 0 0

1
Impossible!

提示

对于25%的数据满足: n*m<=5000;
对于50%的数据满足: n*m<=10000;
对于100%的数据满足: n*m<=20000

原始資料

• Zero1 題號：b114
• Hydro 題號：Z1114
• Locale：zh_CN
• Display：practice