题目描述

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

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

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

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

输入格式

输入包含多个测试用例。

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

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

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

输出格式

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

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

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

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

在此前提下，再按照$\red{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

提示

$\red{1≤N,M≤20}$