#include <stdio.h>
#include <string.h>

#define DEBUGGING 1

#define N 0
#define E 1
#define S 2
#define W 3
#define OPPOSITE(D) (((D)+2) % 4)

#define L 3
#define F 0
#define R 1

typedef struct intsect {
  int    row, col, dir, entrance, goal;
  struct intsect *from, *succ[4], *qp;
} intsect;

intsect maze[10][10][4];
char    maze_id[25], cval[256], tval[256];
FILE    *in_f, *out_f;
int     dval[256], dc[4], dr[4], entr_r, entr_c, entr_dir;


void read_maze (void)
{
  int  r, c, d, dd, goal_x, goal_y;
  char w[10];

  for (r = 0;  r < 10;  ++r) {
    for (c = 0;  c < 10;  ++c) {
      for (d = 0;  d < 4;  ++d) {
	maze[r][c][d].row = r;  maze[r][c][d].col = c;  
	maze[r][c][d].dir = d;  
	maze[r][c][d].entrance = maze[r][c][d].goal = 0;
	maze[r][c][d].from = maze[r][c][d].qp = NULL;
	for (dd = 0;  dd < 4;  ++dd) maze[r][c][d].succ[dd] = NULL;
      }
    }
  }

  fscanf(in_f, "%s", maze_id);
  if (strcmp(maze_id,"END") == 0) return;
  printf("\nChecking maze %s...\n", maze_id);
    
  fscanf(in_f, "%d%d", &entr_r, &entr_c);
  fscanf(in_f, "%s", w);  entr_dir = dval[w[0]];
  maze[entr_r][entr_c][entr_dir].entrance = 1;
  fscanf(in_f, "%d%d", &goal_x, &goal_y);
  for (d = 0;  d < 4;  ++d) maze[goal_x][goal_y][d].goal = 1;

  for (fscanf(in_f, "%d", &r);  r > 0;  fscanf(in_f, "%d", &r)) {
    fscanf(in_f, "%d", &c);
    for (fscanf(in_f, "%s", w);  w[0]!='*';  fscanf(in_f, "%s", w)) {
      char *dp = w;
      int  cur_d, turn, new_d;

      cur_d = dval[*dp++];
      while (*dp) { 
	turn = dval[*dp++];  new_d = (cur_d+turn)%4;
	maze[r][c][OPPOSITE(cur_d)].succ[turn] = 
	  &maze[r+dr[new_d]][c+dc[new_d]][OPPOSITE(new_d)];
      }
    }
  }

#if DEBUGGING
  for (r = 0;  r <= 9;  ++r) {
    for (c = 0;  c <= 9;  ++c) {
      printf("(%d,%d): ", r, c);
      for (d = 0;  d < 4;  ++d) {
	printf("%c%s%s: ", 
	       cval[d],
	       (maze[r][c][d].entrance ? "[E]" : ""),
	       (maze[r][c][d].goal ? "[G]" : ""));
	for (dd = 0;  dd < 4;  ++dd) {
	  intsect *sp = maze[r][c][d].succ[dd];
	  if (sp) printf("%c->(%d,%d)%c ", 
			 tval[dd], sp->row, sp->col, cval[sp->dir]);
	}
      }
      printf("\n");
    }
  }
#endif
}


int pr (intsect *p)
{
  int n_printed = 0;

#if DEBUGGING
  printf("  Is (%d,%d)%c the entrance?\n",
	 p->row, p->col, cval[p->dir]);
#endif
  if (!p->entrance) n_printed = pr(p->from);
  
  if (n_printed%10==0) fprintf(out_f, "\n ");
  fprintf(out_f, " (%d,%d)", p->row, p->col);
  return n_printed+1;
}


void print_solution (intsect *goal)
{
#if DEBUGGING
  printf("Print solution; goal intersection is (%d,%d)%c.\n",
	 goal->row, goal->col, cval[goal->dir]);
#endif
  fprintf(out_f, "%s", maze_id);
  pr(goal);  fprintf(out_f, "\n");
}


void solve_maze (void)
{
  intsect *p, *q, *last_q, *s;
  int     d, n_sol = 0;

  q = last_q = 
    &maze[entr_r+dr[entr_dir]][entr_c+dc[entr_dir]][OPPOSITE(entr_dir)];
  q->from = &maze[entr_r][entr_c][entr_dir];

  while (q) {
    p = q;  q = q->qp;
    printf("Checking intersection (%d,%d)%c:\n", 
	   p->row, p->col, cval[p->dir]);

    if (p->goal) {
      printf("  Arrived at goal.\n");
      if (++n_sol == 1) print_solution(p);  
    }
    if (n_sol > 0) continue;

    for (d = 0;  d < 4;  ++d) {
      if (s = p->succ[d]) {
	if (s->from) {
	  printf("  Gone to (%d,%d)%c previously.\n",
		 s->row, s->col, cval[s->dir]);
	  continue;
	}
	s->from = p;
	printf("  Add new path to (%d,%d)%c.\n",
	       s->row, s->col, cval[s->dir]);
	if (q) { last_q->qp = s;  last_q = s; }
	else   q = last_q = s;
      }
    }
  }
  printf("%d solution(s) found.\n", n_sol);
  if (n_sol==0) fprintf(out_f, "%s\n  No solution possible\n", maze_id);
}


int main (void)
{
  in_f = fopen("maze.in","r");  out_f = fopen("maze.out","w");

  cval[N] = 'N';  dval['N'] = N;  
  cval[E] = 'E';  dval['E'] = E;  
  cval[S] = 'S';  dval['S'] = S;  
  cval[W] = 'W';  dval['W'] = W;
  tval[L] = 'L';  dval['L'] = L;  
  tval[F] = 'F';  dval['F'] = F;  
  tval[R] = 'R';  dval['R'] = R;
  dc[N] = dc[S] = 0;  dc[W] = -1;  dc[E] = 1;
  dr[W] = dr[E] = 0;  dr[N] = -1;  dr[S] = 1;

  for (;;) {
    read_maze();  if (strcmp(maze_id,"END") == 0) break;
    solve_maze();
  }

  fclose(in_f);  fclose(out_f);  return 0;
}