勇士被困在了一张m*n的地图上，可以控制勇士每秒向上、下、左、右任意方向移动一格，之后怪兽会朝着勇士方向移动至多两格。注意怪兽会优先横着走，勇士和怪兽都不会穿墙。勇士的目的地是桥头，但是千万不能被怪兽吃掉。陷阱是很有用的东西（一格），勇士是不能进入陷阱的，但是可以把怪兽引入陷阱，在接下来的三次移动中，怪兽将无法移动，3秒后恢复正常。现在给出地图的信息，请用最少的步数走在桥上。
勇士被困在了一张m*n的地图上，可以控制勇士每秒向上、下、左、右任意方向移动一格，之后怪兽会朝着勇士方向移动至多两格。注意怪兽会优先横着走，勇士和怪兽都不会穿墙。勇士的目的地是桥头，但是千万不能被怪兽吃掉。陷阱是很有用的东西（一格），勇士是不能进入陷阱的，但是可以把怪兽引入陷阱，在接下来的三次移动中，怪兽将无法移动，3秒后恢复正常。现在给出地图的信息，请用最少的步数走在桥上。
第1行是2个正整数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 . . . . . . . .
right right down down down total steps：5
【数据规模】
对于30%的数据满足：n≤5，且没有墙。
对于60%的数据满足：n≤10，且没有陷阱。
对于100%的数据满足：n≤20。
课课通