#include <stdio.h>
#include <stdlib.h>

#define	MAX_ROWS		20
#define	MAX_COLS		20
#define	MAX_PATROL_STATES	12
#define	MAX_MAZE_SIZE		(MAX_ROWS * MAX_COLS)
#define	MAX_CONFIGS		(MAX_PATROL_STATES * (MAX_MAZE_SIZE+1) * (MAX_MAZE_SIZE+1))

const char *moves = "NSEW";

// Koordináty robota v bludišti.
struct scoords {
	char row, col;
};

// Konfigurace robotů a stráží.
struct sconfig {
	unsigned char ticker;	// Tikač určuje, v jaké fázi se nacházejí stráže (počítá modulo 12).
	char move;				// Tah (N, S, E nebo W), kterým jsme se do této konfigurace dostali.
							// X je počáteční konfigurace a \0 je zatím neprozkoumaná konfigurace.
	struct scoords robot[2];
};

// Struktura zapouzdřující frontu konfigurací.
struct sfifo {
	struct sconfig data[MAX_CONFIGS];
	int first, last;
};

// Struktura zapouzdřující jednu stráž.
struct sguard {
	struct scoords start;	// Políčko, na kterém stráž začíná svou hlídku.
	unsigned char len;		// Délka hlídkovací trasy.
	char direction;			// Směr, kterým se stráž na začátku dívá (N, S, E nebo W).
};

/*
 * Stavový prostor všech možných konfigurací. Každá konfigurace ukazuje na předchozí tak,
 * jak byly procházeny v BFS. Dosud nenavštívené konfigurace mají nastavený move na \0.
 */
struct sconfig configs[MAX_PATROL_STATES][MAX_MAZE_SIZE+1][MAX_MAZE_SIZE+1];

// Jednotlivá bludiště (hodnota 0 = volné pole, 1 = zeď).
char mazes[2][MAX_ROWS][MAX_COLS];
int rows[2], cols[2];

// Seznam stráží.
struct sguard guards[2][10];
int guardsCount[2];

// Fronta konfigurací.
struct sfifo fifo;

// Pole pro výsledky.
char results[MAX_CONFIGS];
int resultsCount = 0;

/*
 * Souřadnice a směry.
 */

// Převede znak reprezentující světovou stranu na relativní koordináty pro pohyb.
inline struct scoords getDirectionCoords(char direction) {
	struct scoords res;
	res.row = res.col = 0;
	switch(direction) {
		case 'N':	res.row = -1;	break;
		case 'S':	res.row = 1;	break;
		case 'E':	res.col = 1;	break;
		case 'W':	res.col = -1;	break;
	}
	return res;
}

// Otestuje, zda je robot venku z bludiště.
inline int isRobotOut(struct scoords robot) {
	return (robot.row < 0) ? 1 : 0;
}

// Vrací true, pokud jsou si koordináty rovny. Jinak vrací false.
inline int isEqual(struct scoords coords1, struct scoords coords2) {
	return (coords1.row == coords2.row) && (coords1.col == coords2.col);
}

// Posune robota daným směrem (pokud je to možné).
inline void moveRobot(struct scoords *robot, struct scoords direction, int mazeIdx) {
	if (isRobotOut(*robot)) return;
	struct scoords newPos = *robot;
	newPos.row += direction.row;
	newPos.col += direction.col;
	if ((newPos.row < 0) || (newPos.col < 0) || (newPos.row >= rows[mazeIdx]) || (newPos.col >= cols[mazeIdx]))
		robot->row = -1;
	else if (mazes[mazeIdx][(unsigned)newPos.row][(unsigned)newPos.col] == 0)
		*robot = newPos;
}

/*
 * Práce se stavovým prostorem konfigurací.
 */

// Zakóduje pozici robota do integeru. Bere ohled na to, že robot může být mimo bludiště.
inline int encodeCoords(struct scoords coords) {
	int res = coords.row * MAX_COLS + coords.col;
	if (coords.row < 0) res = MAX_MAZE_SIZE;	// Pokud je robot mimo bludiště.
	return res;
}

// Označí danou konfiguraci za zpracovanou.
inline void markConfigVisited(struct sconfig C, struct sconfig Prev, char move) {
	struct sconfig *config = &configs[C.ticker][ encodeCoords(C.robot[0]) ][ encodeCoords(C.robot[1]) ];
	*config = Prev;
	config->move = move;
}

// Podívá se na stav dané konfigurace.
inline unsigned char isConfigVisited(struct sconfig C) {
	return (configs[C.ticker][ encodeCoords(C.robot[0]) ][ encodeCoords(C.robot[1]) ].move != '\0');
}

// Nalezne následující konfiguraci když se roboti hýbou daným směrem.
inline struct sconfig getNextConfig(struct sconfig config, char move) {
	struct scoords direction = getDirectionCoords(move);
	struct sconfig res = config;
	res.ticker = (res.ticker + 1) % 12;
	for(int i = 0; i < 2; i++)
		moveRobot(&res.robot[i], direction, i);
	return res;
}

/*
 * Práce s FIFO.
 */

// Inicializuje frontu.
inline void initFifo(struct sfifo *F) {
	F->last = -1;
	F->first = 0;
}

// Pokud je fronta prázdná, vrací true, jinak false.
inline int isFifoEmpty(struct sfifo *F) {
	return (F->last < F->first);
}

// Vloží prvek C do fifo.
inline void pushFifo(struct sfifo *F, struct sconfig C) {
	F->data[ ++F->last ] = C;
}

// Vyjme prvek z fronty a uloží jej do C. Pokud se to povedlo, vrací true, jinak false.
inline int popFifo(struct sfifo *F, struct sconfig *C) {
	if (isFifoEmpty(F)) return 0;
	*C = F->data[ F->first++ ];
	return 1;
}

/*
 * Stráže.
 */

// Vypočítá pozici stráže podle časovače.
inline struct scoords getGuardPos(struct sguard guard, unsigned char ticker) {
	ticker %= (guard.len - 1) * 2;
	struct scoords res = guard.start;
	struct scoords direction = getDirectionCoords(guard.direction);
	int len = (guard.len-1) - abs(ticker - guard.len + 1);
	res.row += direction.row * len;
	res.col += direction.col * len;
	return res;
}

// Otestuje, zda došlo při přesunu do nové konfigurace k polapení některého z robotů.
inline int isCaptured(struct sconfig config, struct sconfig newConfig) {
	struct scoords pos1, pos2;
	for(int i = 0; i < 2; i++)
		if (!isRobotOut(config.robot[i]))
			for(int g = 0; g < guardsCount[i]; g++) {
				pos1 = getGuardPos(guards[i][g], config.ticker);
				pos2 = getGuardPos(guards[i][g], newConfig.ticker);
				if (isEqual(pos2, newConfig.robot[i]) ||
						(isEqual(pos1, newConfig.robot[i]) && isEqual(pos2, config.robot[i])))
					return 1;
			}
	return 0;
}

/*
 * Hlavní procedury.
 */

// Načte z daného souboru jedno bludiště a jeho sttáže.
void loadMaze(FILE *fp, struct scoords *robot, int mazeIdx) {
	
	// Načteme rozměry.
	fscanf(fp, "%d %d\n", &rows[mazeIdx], &cols[mazeIdx]);
	
	// Načteme mapu bludiště.
	char ch;
	for(int i = 0; i < rows[mazeIdx]; i++) {
		for(int j = 0; j < cols[mazeIdx]; j++) {
			fscanf(fp, "%c", &ch);
			switch(ch) {
				case '#':	// Nastavíme pole na stěnu.
					mazes[mazeIdx][i][j] = 1;
					break;
				
				case 'X':	// Označíme počáteční pozici.
					robot->row = i;
					robot->col = j;
					// A tady propadneme do následujícího case...
				case '.':	// Nastavíme pole jako volné.
					mazes[mazeIdx][i][j] = 0;
					break;
			}
		}
		fscanf(fp, "\n");
	}
	
	// Načteme stráže.
	fscanf(fp, "%d\n", &guardsCount[mazeIdx]);
	for(int i = 0; i < guardsCount[mazeIdx]; i++) {
		int row, col, len;
		fscanf(fp, "%d %d %d %c\n", &row, &col, &len, &guards[mazeIdx][i].direction);
		guards[mazeIdx][i].start.row = row - 1;
		guards[mazeIdx][i].start.col = col - 1;
		guards[mazeIdx][i].len = len;
	}
}

// Načteme data ze vstupního souboru.
void load(void) {
	FILE *fp = fopen("robots.in", "r");
	if (!fp) exit(1);

	struct sconfig config;
	config.ticker = 0;
	for(int i = 0; i < 2; i++)
		loadMaze(fp, &config.robot[i], i);

	fclose(fp);
	pushFifo(&fifo, config);
	configs[0][ encodeCoords(config.robot[0]) ][ encodeCoords(config.robot[1]) ].move = 'X';
}

// Pustí nad daným bludištěm prohledávání do šířky.
void bfs(void) {
	struct sconfig config, newConfig;
	while(popFifo(&fifo, &config)) {
		for(int i = 0; i < 4; i++) {
			newConfig = getNextConfig(config, moves[i]);
			if (!isConfigVisited(newConfig) && !isCaptured(config, newConfig)) {
				markConfigVisited(newConfig, config, moves[i]);
				if (isRobotOut(newConfig.robot[0]) && isRobotOut(newConfig.robot[1]))
					return;
				pushFifo(&fifo, newConfig);
			}
		}
	}
}

// Zapíše výsledky do souboru.
void writeResults(void) {
	FILE *fp = fopen("robots.out", "w");
	if (!fp) return;
	
	// Projdeme možné koncové stavy.
	int i = 0;
	while((i < MAX_PATROL_STATES) && (configs[i][MAX_MAZE_SIZE][MAX_MAZE_SIZE].move == 0))
		i++;
	
	// Neexistuje korektní řešení.
	if (i == MAX_PATROL_STATES) {
		fprintf(fp, "-1\n");
		return;
	}
	
	// Projdeme cestu zpet k pocatecnimu stavu.
	struct sconfig *config = &configs[i][MAX_MAZE_SIZE][MAX_MAZE_SIZE];
	while(config->move != 'X') {
		results[resultsCount++] = config->move;
		config = &configs[config->ticker][ encodeCoords(config->robot[0]) ][ encodeCoords(config->robot[1]) ];
	}
	
	// Nalezenou cestu zapíšeme v opačném pořadí do souboru.
	fprintf(fp, "%d\n", resultsCount);
	while(resultsCount-- > 0)
		fprintf(fp, "%c\n", results[resultsCount]);
}

int main(void) {
	initFifo(&fifo);	
	load();
	bfs();
	writeResults();
    return 0;
}