题目描述

推箱子游戏相信大家都不陌生，在本题中，你将控制一个人把 $1$ 个箱子推到目的地。

给定一张 $N$ 行 $M$ 列的地图，用字符 . 表示空地，字符 # 表示墙，字符 S 表示人的起始位置，字符 B 表示箱子的起始位置，字符 T 表示箱子的目标位置。

求一种移动方案，使箱子移动的次数最少，在此基础上再让人移动的总步数最少。

方案中使用大写的 EWSN（东西南北）表示箱子的移动，使用小写的 ewsn（东西南北）表示人的移动。

输入格式

输入包含多个测试用例。

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

接下来 $N$ 行，每行包括 $M$ 个字符，用以描绘整个 $N$ 行 $M$ 列的地图。

当样例为 $N=0, M=0$ 时，表示输入终止，且该样例无需处理。

输出格式

对于每个测试用例，第一行输出 Maze # + 测试用例的序号。

第二行输入一个字符串，表示推箱子的总体移动过程，若无解，则输出 Impossible.。

每个测试用例输出结束后输出一个空行。

若有多条路线满足题目要求，则按照 N、S、W、E 的顺序优先选择箱子的移动方向（即先上下推，再左右推）。

在此前提下，再按照 n、s、w、e 的顺序优先选择人的移动方向（即先上下动，再左右动）。

样例

输入样例：

1 7
SB....T
1 7
SB..#.T
7 11
###########
#T##......#
#.#.#..####
#....B....#
#.######..#
#.....S...#
###########
8 4
....
.##.
.#..
.#..
.#.B
.##S
....
###T
0 0

输出样例：

Maze #1
EEEEE

Maze #2
Impossible.

Maze #3
eennwwWWWWeeeeeesswwwwwwwnNN

Maze #4
swwwnnnnnneeesssSSS

样例解释

Maze #1：地图 SB....T，宽度为 7，箱子从 B 到 T 只需一直向右推即可，箱子移动 5 次，用大写 E 表示，人的移动不输出因为人的移动已经隐含在推箱子的准备中（输出的是总体移动过程，包括人移动到推箱子位置的移动和推箱子移动）。
样例输出 EEEEE 表示箱子向右移动了 5 次。

Maze #2：地图 SB..#.T，中间有墙 # 阻挡，箱子无法推到目标位置，输出 Impossible.。

Maze #3 和 Maze #4 类似，是复杂地图中的移动方案。

数据范围

• $1 \le N, M \le 20$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB