No testdata at current.

题目描述

有一个 $N\times M$ 的矩阵，每个位置可能是硬地（用 . 表示），易碎地面（用 E 表示），禁地（用 # 表示），起点（用 X 表示），终点（用 O 表示）。

你的任务是操作一个 $1\times1\times2$ 的长方体。

这个长方体在地面上有两种放置方式，" 立 " 在地面上（ $1\times1$的面接触地面）或者 " 躺 " 在地面上（$1\times 2$ 的面接触地面）。

在每一步操作中，可以按上下左右的四个键之一。

按下按键之后，长方体向对应的方向沿着棱滚动$90°$ 。

任意时刻，长方体不能有任何部位接触禁地，并且不能立在易碎地面上。

字符 X 标识长方体的起始位置，地图上可能有一个 X 或者两个相邻的 X。

地图上唯一的一个字符 O 标识目标位置。

求把长方体移动到目标位置（即立在 O 上）所需要的最少步数。

在移动过程中，X 和 O 的表示位置都可以看作是硬地被利用。

输入格式

输入包含多组测试用例。

对于每个测试用例，第一行包括两个整数 $N$ 和 $M$。

接下来 $N$ 行用来描述地图，每行包括 $M$个字符，每个字符表示一块地图的具体状态。

当输入用例 $N=0,M=0$ 时，表示输入终止，且该用例无需考虑。

输出格式

每个用例输出一个整数表示所需的最少步数，如果无解则输出 Impossible。

每个结果占一行。

样例

样例输入

7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######
0 0

样例输出

10

数据范围与提示

对于 $100\%$ 的数据，有 $3\le N,M\le500$。