/* Contest   : SWERC 97
 * Problem E : Pushing Boxes
 * Version   : minimize pushes first, then minimize walks
 * Method    : Generalized breadth-first search             
 * Author    : Mark Dettinger
 * Date      : 11.11.97

A state consists of the position of the man and the box.
We define the distance of a state from the beginning state as
10000 * number of pushes + number of walks needed to reach it.
We need a queue of states and three pointers: head, tail and mid.

queue:  aaaaaaaaaaaaaabbbbbbbbbbbbbbbb
        ^             ^               ^
       head          mid             tail

Head and tail have the usual meaning.
The elements between mid and tail are the newest elemnts in the queue.
Their successor states are not in the queue yet.
The elements between head and mid are older. Their successor states reachable by walks
are already in the queue, but their successor states reachable by pushes are not.

Now in each iteration the question is:
What leads to the smaller state? To do a push with the state the head pointer points to
or to do the walks with the state pointed to by the mid pointer?
Make your choice, then increment either head or mid,
and insert the successor states at the tail. */

#include <stdio.h>

#define WHITE 0
#define GRAY 1
#define BLACK 2
#define oo 1000000000
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define DBG(x)

typedef struct { char mani,manj,boxi,boxj; } state;

FILE* input;
int kase=0;
int rows,cols;
char maze[32][32];
int d[32][32][32][32];
char color[32][32][32][32];
char pred[32][32][32][32];
int pos[32][32][32][32];

state queue[160008];
int head,mid,tail;

void skip_line() { while (fgetc(input)!='\n'); }

void enqueue (int mi, int mj, int bi, int bj)
{
  DBG(printf("enqueue %d %d %d %d\n",mi,mj,bi,bj));
  color[mi][mj][bi][bj] = GRAY;
  queue[tail].mani = mi;
  queue[tail].manj = mj;
  queue[tail].boxi = bi;
  queue[tail].boxj = bj;
  tail++;
}

int dequeue (int *mi, int *mj, int *bi, int *bj)
{
  int mi1,mj1,bi1,bj1,mi2,mj2,bi2,bj2,d1,d2;

  mi1 = queue[head].mani;
  mj1 = queue[head].manj;
  bi1 = queue[head].boxi;
  bj1 = queue[head].boxj;
  d1 = d[mi1][mj1][bi1][bj1];
  if (mid!=tail)
    {
      mi2 = queue[mid].mani;
      mj2 = queue[mid].manj;
      bi2 = queue[mid].boxi;
      bj2 = queue[mid].boxj;
      d2 = d[mi2][mj2][bi2][bj2];
    }

  /*  Now make the choice leading to the lowest state:
   *  do push for the state the head-pointer points to
   *  - OR -
   *  do walks for the state the mid-pointer points to
   */

  if (mid==tail || d1+10000<d2+1)
    {
      *mi = mi1;
      *mj = mj1;
      *bi = bi1;
      *bj = bj1;
      head++;
      return 1;  /* prepare for push */
    }
  else
    {
      *mi = mi2;
      *mj = mj2;
      *bi = bi2;
      *bj = bj2;
      mid++;
      return 2;  /* prepare for walks */
    }
}

void visit (int mi, int mj, int bi, int bj, int dist, char from)
{
  if (mi<0 || mi>= rows || mj<0 || mj>=cols ||
      bi<0 || bi>= rows || bj<0 || bj>=cols ||
      (mi==bi && mj==bj) || 
      maze[mi][mj]=='#' || maze[bi][bj]=='#' ||
      color[mi][mj][bi][bj]!=WHITE) return;
  d[mi][mj][bi][bj] = dist;
  pred[mi][mj][bi][bj] = from;
  enqueue(mi,mj,bi,bj);
}

void printpath (int mi, int mj, int bi, int bj)
{
  switch (pred[mi][mj][bi][bj])
    {
    case 'n' : printpath(mi+1,mj,bi,bj); printf("n"); break;
    case 's' : printpath(mi-1,mj,bi,bj); printf("s"); break;
    case 'e' : printpath(mi,mj-1,bi,bj); printf("e"); break;
    case 'w' : printpath(mi,mj+1,bi,bj); printf("w"); break;
    case 'N' : printpath(mi+1,mj,bi+1,bj); printf("N"); break;
    case 'S' : printpath(mi-1,mj,bi-1,bj); printf("S"); break;
    case 'E' : printpath(mi,mj-1,bi,bj-1); printf("E"); break;
    case 'W' : printpath(mi,mj+1,bi,bj+1); printf("W"); break;
    } 
}

int main()
{ 
  int mani,manj,boxi,boxj,targeti,targetj,mode;
  int dist,i,j,ii,jj;

  input = fopen("pushing.in","r");
  while (1)
    {
      fscanf(input,"%d %d",&rows,&cols);
      if (rows==0 && cols==0) break;
      skip_line();
      printf("Maze #%d\n",++kase);
      for (i=0; i<rows; i++)
	{
	  fgets(maze[i],32,input);
	  DBG(printf("%s",maze[i]));
	}
      for (i=0; i<rows; i++)
	for (j=0; j<cols; j++)
	  {
	    for (ii=0; ii<rows; ii++)
	      for (jj=0; jj<cols; jj++)
		{
		  d[i][j][ii][jj] = oo;
		  color[i][j][ii][jj] = WHITE;
		}
	    if (maze[i][j]=='S')
	      {
		mani = i;
		manj = j;
	      }
	    if (maze[i][j]=='B')
	      {
		boxi = i;
		boxj = j;
	      }
	    if (maze[i][j]=='T')
	      {
		targeti = i;
		targetj = j;
	      }
	  }
      head = mid = tail = 0;
      visit(mani,manj,boxi,boxj,0,'-');
      while (head!=tail)
	{
	  mode = dequeue(&mani,&manj,&boxi,&boxj);
	  if (boxi==targeti && boxj==targetj) break;
	  dist = d[mani][manj][boxi][boxj];
	  if (mode==1)
	    {
	      if (mani-1==boxi && manj==boxj)
		visit(mani-1,manj,boxi-1,boxj,dist+10000,'N');
	      if (mani+1==boxi && manj==boxj)
		visit(mani+1,manj,boxi+1,boxj,dist+10000,'S');
	      if (mani==boxi && manj-1==boxj)
		visit(mani,manj-1,boxi,boxj-1,dist+10000,'W');
	      if (mani==boxi && manj+1==boxj)
		visit(mani,manj+1,boxi,boxj+1,dist+10000,'E');	 
	    }
	  else if (mode==2)
	    {
	      visit(mani-1,manj,boxi,boxj,dist+1,'n');
	      visit(mani+1,manj,boxi,boxj,dist+1,'s');
	      visit(mani,manj-1,boxi,boxj,dist+1,'w');
	      visit(mani,manj+1,boxi,boxj,dist+1,'e');	      
	    }
	}
      if (boxi==targeti && boxj==targetj)
	{
	  printpath(mani,manj,targeti,targetj);
	  printf("\n\n");
	}
      else
	{
	  printf("Impossible.\n\n");
	}
    }
  return 0;
}