题目描述

​ 勇士被困在了一张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”。

样例数据

input

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 . .

. . . . . .

output

right

right

down

down

down

total steps:5

友情提醒

1)怪物掉进了陷阱后，如果时间到，则不会接着再掉进去。

2)怪物掉进了陷阱，时间到了，如果没动，则不算再掉入。

3)一旦勇士到达桥头，那么他就胜利了，不需要再计算怪兽。

4)怪兽在不能横着走的情况下会竖着走，如果不能竖着走就不动(即如果勇士在它左上角，则它只会向左或向上)。

数据规模与约定

时间限制：$1 \text{s}$

空间限制：$256 \text{MB}$