program vj1044;

const

dir:array[1..4,1..2]of longint=((-1,0),(0,-1),(0,1),(1,0));

var

i,j,k,m,n,ex,ey,wx,wy,s,t,x,y,z,xx,yy:longint;

map:array[1..20,1..20]of longint;

b:array[1..20,1..20,1..20,1..20,0..3]of boolean;

q:array[1..160000,1..8]of longint;

ch:char;

procedure init;

begin

fillchar(q,sizeof(q),0);

readln(m,n);

for i := 1 to m do

for j := 1 to n do

read(map);

for i := 1 to m do

begin

for j := 1 to n do

begin

read(ch);

case ch of

'S':begin

q[1,1]:=i;

q[1,2]:=j;

end;

'M':begin

q[1,3]:=i;

q[1,4]:=j;

end;

'W':begin

wx:=i;

wy:=j;

end;

'E':begin

ex:=i;

ey:=j;

end;

end;

end;

readln;

end;

fillchar(b,sizeof(b),false);

b[q[1,1],q[1,2],q[1,3],q[1,4],0]:=true;

s:=0;t:=1;

end;

procedure work;

begin

while syy)and(map[x,y] and 2=0) then dec(y)

else

if (yxx)and(map[x,y] and 1=0) then dec(x)

else

if (x0 then

begin

z:=q-1;

x:=q;

y:=q;

end;

if (not b[xx,yy,x,y,z])and((xx x) or (yy y))

or((xx = ex) and (yy = ey)) then

begin

b[xx,yy,x,y,z]:=true;

inc(t);

q[t,1]:=xx;

q[t,2]:=yy;

q[t,3]:=x;

q[t,4]:=y;

q[t,5]:=z;

q[t,6]:=s;

q[t,7]:=i;

q[t,8]:=q+1;

if (xx = ex) and (yy = ey) then exit;

end;

end;

j:=j*2;

end;

end;

end;

procedure print(x:longint);

begin

if q[x,6]0 then print(q[x,6]);

case q[x,7] of

1:writeln('up');

2:writeln('left');

3:writeln('right');

4:writeln('down');

end;

end;

begin

assign(input,'mmk.in');

reset(input);

init;

work;

if (xx = ex) and (yy = ey)

then

begin

print(t);

writeln('total steps: ',q[t,8]);

end

else writeln('impossible');

close(input);

end.

15分的程序