第一行是两个正整数m,n(m,n< =20),表示地图的大小为m*n.
接下来是n行，每行m个整数,表示一个格子周围墙的信息。其中
1-上方有墙
2-左方有墙
4-右方有墙
8-下方有墙
例如，一个格子的左、上、右都有墙，那么代表这个格子的整数是2+1+4=7。
接下来是n行，每行m个字符，表示一个格子里的其他信息，其中
.-nothing
S-勇士的初始位置
W-陷阱
M-怪兽的初始位置
E-目的地，即桥头
其中S,M,E均保证只出现一次。
输出包含若干行，前r行为最少步数走到桥头的走法，每行为up,down,left,right中的一个，表示勇士的走法。最后一行输出最少步数r，格式见样例。
若存在多解，按照上左右下的优先顺序行走。
若无法走到桥头，只输出一行impossible。
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.. ......· \n ·· ·· ·· ·· ·· \n ·· ·· ·· ·· ·· \n ·· ·· ·· ·· ·· \n ·· ·· ·· ·· ·· \n · ·· ·· · ·· \n ·· ·· ·· ·· ·· \n \n \n \n \n \n \n
right right down down down total steps: 5\n \n \n \n \n · · \n