sah

Ana and Ion have a common passion for chess and they play chess whenever they have free time. Being original persons, they ordered chess boards of various sizes, and special chess piece sets. If they don't have the time to finish a game, they keep the pieces on the chess board as they are, and continue the next day.
This time, they have a problem - Ionel, their son, accidentally knocked over the chess board - and they are trying to recreate the last configuration on the chess board.
Ion precisely remembers how the configuration of the chessboard looked yesterday at the beginning of the game, as well as the moves he made. Ana remembers that she played kind of odd - the entire game she kept moving the same piece, a rook. She doesn't exactly remember the positions she moved to, but she remembers the directions in which she moved the rook.

Task

Write a program that determines the positions in which the rook Ana was moving could be located.

Input Data

Input file sah.in contains on line one two positive integers separated by a space, X N, representing the size of the chessboard, and respectively the number of pieces on the chess board.
The following N lines contain information regarding the position of the chess pieces. More specifically, line i+1 contains the position of piece i in the form of two positive integers separated by a space, L C, representing the line and respectively the column on which the piece is located.
The last position corresponds to the rook Ana was moving.
The next line contains a positive integer Nr, which represents the number of moves Ion and respectively Ana made.
Each of the following Nr lines contains information about the moves Ion made.
More specifically, line N+2+j contains 3 positive integers separated by a space, i L1 C1, with the meaning that piece i is moved to line L1, column C1.
The last line of the file contains a sequence of Nr characters of set {'N', 'S', 'E', 'V'} which represents the directions in which Ana moved the rook (character i of this sequence corresponds to the i-th move).

Output Data

Output file sah.out will contain on line one a positive integer p, representing the number of possible final positions.
The following p lines contain the possible final positions, one on each line. A position is described by two positive integers separated by a space, L C, with the meaning that "a final possible position is on line L and column C". The final positions will be written in order of the lines; if there is more than one final position on the same line, these will be written in order of the columns.

Constraints and Statements

1 < X <= 50
1 < N <= 1000
0 < Nr <= 1000
The pieces are numbered from 1 to N.
The lines of the chess board are numbered from top to bottom from 1 to X, and the columns are numbered from left to right from 1 to X.
Ana and Ion move alternately; Ion had the first move.
A rook can be moved only in 4 directions:
north (coded N) - on a line with a smaller index, on the same column;
south (coded S) - on a line with a bigger index and on the same column
east (coded E) - on a column with a bigger index and on the same line
west (coded V) - on a column with a smaller index and on the same line
For a move a piece has to move from the current position.

Time limit: 0.1 seconds/test

prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
Contact:emanuela.cerchez@gmail.com