/* Contest   : SWERC 97
 * Problem ? : Sokoban - Light
 * Method    : sorted generation
 * Author    : Falk Bartels
 * Date      : 20.10.97
 */

#include <stdio.h>

#define DBG(x)

#define UNVISITED -1
#define MAXDIM 20
#define MAXSTATES (20*20*20*20)
#define SENTINEL MAXSTATES
#define MAXSOL 1000

#define START 'f'
#define LEFTMOVE 'w'
#define RIGHTMOVE 'e'
#define UPMOVE 'n'
#define DOWNMOVE 's'
#define LEFTPUSH 'W'
#define RIGHTPUSH 'E'
#define UPPUSH 'N'
#define DOWNPUSH 'S'

#define MAN 'S'
#define BOX 'B'
#define GOAL 'T'
#define SPACE '.'
#define WALL '#'

#define oo 1000000

FILE *input;

int maxx, maxy;

char field[MAXDIM+2][MAXDIM+2];
int manx, many, boxx, boxy, goalx, goaly;

struct { int pushes, moves; char dir;} states[MAXSTATES+1];

int queue[MAXSTATES];
int q_next;


int readcase()
{
  char c;
  int x, y;

  fscanf( input, "%d %d ", &maxy, &maxx );
  if (maxx==0 && maxy==0) return 0;

  for (x=maxx+1; x>=0; x--) field[x][0]=field[x][maxy+1]=WALL;
  for (y=maxy; y>0; y--){
    field[0][y]=field[maxx+1][y]=WALL;
    for (x=1; x<=maxx; x++) {
      fscanf( input, "%c ", &c);
      if      (c==MAN) { manx=x;   many=y;   field[x][y]=SPACE;}
      else if (c==BOX) { boxx=x; boxy=y; field[x][y]=SPACE;}
      else if (c==GOAL) { goalx=x;  goaly=y;  field[x][y]=SPACE;}
      else if (c==SPACE) field[x][y]=SPACE;
      else if (c==WALL) field[x][y]=WALL;
      else { printf("error reading input\n"); exit(1); }
    }
  }

DBG( printf("Man: (%d,%d) Box: (%d,%d) Goal: (%d,%d)\n",
	    manx, many, boxx, boxy, goalx, goaly  );
     for (y=0; y<=maxy+1; y++) {       
       for (x=0; x<=maxx+1; x++)
         printf("%c", field[x][y]);
       printf("\n");
     }
     printf("\n");
   )

  return 1;
}

int pos2int( int px, int py, int bx, int by)
/* computes a unique state-number for a state given as
   (x,y)-coordinates of the man and the box */
{
  return ((((px-1)*maxy+(py-1))*maxx+(bx-1))*maxy+(by-1));
}

void int2pos( int st, int * px, int * py, int * bx, int * by)
/* the inverse function of the one above */
{
  *by = (st % maxy)+1;
  st /= maxy;
  *bx = (st % maxx)+1;
  st /= maxx;
  *py = (st % maxy)+1;
  st /= maxy;
  *px = st         +1;
}

void visit( int st, int pu, int mo, char d)
/* test, whether the state 'st' has already been reached.
   If not, append it to the queue as found after 'pu' pushes
   and 'mo' moves, comming from direction 'd' */
{

  /* append state to queue, if as yet unvisited */
  if (states[st].pushes==UNVISITED) {
    states[st].pushes=pu;
    states[st].moves=mo;
    states[st].dir=d;
    queue[q_next++]=st;
    queue[q_next]=SENTINEL;
  }
}

void solvecase( int kase)
{
  int px, py, bx, by;
  int st, l;
  int next_move, next_push;
  char c;
  char outstring[MAXSOL];

/* init */

  /* states */
  for (l=0, st=pos2int(maxx,maxy,maxx,maxy); l<st; l++)
    states[l].pushes=UNVISITED;

  /* starting state */
  q_next=next_push=next_move=0;
  visit( st = pos2int( manx, many, boxx, boxy), 0, 0, START);

  printf( "Maze #%d\n", kase);

/* search */
  while (1) {
    
    if (next_push==q_next && next_move==q_next) {
      /* queue is empty before a final state has been found */
      printf("Impossible.\n\n");
      return;
    }
    
    /* undertake the action leading to lowest state */
    if (states[queue[next_move]].pushes<states[queue[next_push]].pushes+1 ||
	(states[queue[next_move]].pushes==states[queue[next_push]].pushes+1 &&
	 states[queue[next_move]].moves+1<states[queue[next_push]].moves)) { 

      /* make moves */
      int2pos( st = queue[next_move], &px, &py, &bx, &by);

      if (field[px+1][py]==SPACE && (px+1!=bx || py!=by) )
	visit( pos2int(px+1,py,bx,by),
	       states[st].pushes, states[st].moves+1, RIGHTMOVE);
      if (field[px-1][py]==SPACE && (px-1!=bx || py!=by) )
	visit( pos2int(px-1,py,bx,by),
	       states[st].pushes, states[st].moves+1, LEFTMOVE);
      if (field[px][py+1]==SPACE && (px!=bx || py+1!=by) )
	visit( pos2int(px,py+1,bx,by),
	       states[st].pushes, states[st].moves+1, UPMOVE);
      if (field[px][py-1]==SPACE && (px!=bx || py-1!=by) )
	visit( pos2int(px,py-1,bx,by),
	       states[st].pushes, states[st].moves+1, DOWNMOVE);

      next_move++;

    } else {

      /* make push, if possible. Test if final state reached. */
      int2pos( st = queue[next_push], &px, &py, &bx, &by);

      if        (px+1==bx && py==by && field[bx+1][by]==SPACE) {
	visit( pos2int(px+1,py,bx+1,by),
	      states[st].pushes+1, states[st].moves, RIGHTPUSH);
	if (bx+1==goalx && by==goaly) break;

      } else if (px-1==bx && py==by && field[bx-1][by]==SPACE) {
	visit( pos2int(px-1,py,bx-1,by),
	      states[st].pushes+1, states[st].moves, LEFTPUSH);
	if (bx-1==goalx && by==goaly) break;

      } else if (px==bx && py+1==by && field[bx][by+1]==SPACE) {
	visit( pos2int(px,py+1,bx,by+1),
	       states[st].pushes+1, states[st].moves, UPPUSH);
	if (bx==goalx && by+1==goaly) break;

      } else if (px==bx && py-1==by && field[bx][by-1]==SPACE) {
	visit( pos2int(px,py-1,bx,by-1),
	       states[st].pushes+1, states[st].moves, DOWNPUSH);
	if (bx==goalx && by-1==goaly) break;
      }

      next_push++;
    }
    
  }

  /* the state just discovered is a final state */  
  st = queue[q_next-1];

  /* Trace solution */ 
  for (l=states[st].pushes+states[st].moves, outstring[l]=0; l>0; l--) {
    outstring[l-1] = c = states[st].dir;
    int2pos( st, &px, &py, &bx, &by);      
    if      (c==LEFTMOVE ) px++;
    else if (c==RIGHTMOVE) px--;
    else if (c==DOWNMOVE ) py++;
    else if (c==UPMOVE   ) py--;
    else if (c==LEFTPUSH ) { px++; bx++; }
    else if (c==RIGHTPUSH) { px--; bx--; }
    else if (c==DOWNPUSH ) { py++; by++; }
    else if (c==UPPUSH   ) { py--; by--; }
    st=pos2int( px, py, bx, by);
  }
  printf("%s\n\n", outstring);

}

int main()
{
  int kase=0;

  states[SENTINEL].pushes = oo;

  if ((input = fopen("pushing.in","r")) == NULL) {
    printf("no input!\n");
    return 1;
  }

  while (readcase()) solvecase( ++kase); 

  fclose(input);
  return 0;
}