Back and Forth

The neighborhood kids invented another odd game. Everybody runs back and forth inside a marked field, and nobody may turn at will: every step goes straight along one of the four compass directions.

The field is a grid of $M$ columns and $N$ rows. A position is a pair $(x, y)$ with $0 \le x < M$ and $0 \le y < N$, and $(0, 0)$ is the bottom-left corner. A step N raises $y$ by one, a step S lowers $y$ by one, a step E raises $x$ by one, and a step W lowers $x$ by one.

The rules are as follows.

• Before the game starts, one kid is chosen to be "it".
• The game runs for a fixed number of rounds. In each round every player takes exactly one step in the direction they are facing, and all players step at the same time.
• A player whose next step would leave the field reverses direction before taking that step. N and S are opposites, and so are E and W.
• Once everybody has stepped, look at the squares holding more than one player. If three or more players share a square, all of them reverse direction. If exactly two share a square, they trade directions like this: the player with the longer name turns to face the direction the other one just stepped in, and the player with the shorter name turns to face the reverse of the direction the longer-named player just stepped in. Both new directions are read off the step that just finished. The rule works because no two kids in the neighborhood have names of the same length.
• After the last round the winner is the player other than "it" whose straight-line distance to "it" is smallest. If two players are equally close, the one with the shorter name wins.

John finds the game silly, because the starting layout already settles the outcome. Write the program that works out the winner for him, so he can show the other kids and talk them into playing something better.

The figure below shows the starting layout of the first sample game.

The first line holds the number of games $T$. Each game is given as follows.

The first line of a game holds three integers $M$, $N$, and $P$: the width of the field, its height (both counted in squares), and the number of players.

Each of the next $P$ lines holds a name, the $x$ and $y$ coordinates of that player's starting square, and the direction the player faces at the start, separated by spaces. The direction is one of N, S, E, and W. No two players start on the same square, and the player listed first is "it".

The last line of a game holds the number of rounds $R$.

Constraints:

• $1 \le T \le 100$
• $2 \le M \le 9$, $2 \le N \le 9$
• $2 \le P \le 9$ and $P \le M \times N$
• $0 \le x < M$, $0 \le y < N$
• $1 \le R \le 1000$
• Every name is 1 to 20 English letters, and within one game no two names have the same length.

For each game print one line reading Case x: name, where $x$ is the number of the game counting from 1 and name is the winner's name.