题目描述

勇士每秒向上、下、左、右移动一格，不能穿墙、越界、走入陷阱或怪兽所在格。随后怪兽向勇士连续追赶至多两格：每一步优先朝勇士的列横向移动，若不能横向靠近则朝勇士的行纵向移动，仍不能则停留。怪兽碰到勇士即失败。

怪兽进入陷阱立即停止，并在接下来三个回合中不能移动；之后恢复。停在陷阱中不算再次掉入，离开后重新进入才会再触发。勇士一到达桥头便立即胜利，不再计算怪兽行动。求最少步数的逃生方案。

输入格式

第一行列数 $m$ 和行数 $n$。接下来 $n$ 行，每行 $m$ 个0至15的整数，表示周围墙：上1、左2、右4、下8，将存在的墙对应数字相加。相邻两格对同一堵墙的描述一致。再给出 $n$ 行字符，每行 $m$ 个；. 为空地，S 为勇士，M 为怪兽，W 为陷阱，E 为桥头；S,M,E 各一个。

输出格式

无解输出 impossible。否则每行一个方向 up、left、right、down；最短方案不唯一时按上、左、右、下的优先次序选择。最后一行输出 total steps:r，其中 $r$ 是最少步数。

样例

6 6
0 8 8 8 8 0
4 3 1 1 5 2
4 2 0 4 6 2
4 2 0 4 6 2
4 10 8 8 12 2
0 1 1 1 1 0
......
.S..W.
....M.
......
...E..
......

right
right
down
down
down
total steps:5

数据范围

对于30%的数据，$m,n\le5$ 且没有墙和陷阱；对于60%的数据，$m,n\le10$ 且没有陷阱；对于100%的数据，$1\le m,n\le20$，$mn\ge3$。