왕복 술래잡기

동네 아이들이 또 희한한 놀이를 만들어 냈다. 모두 정해진 구역 안을 왔다 갔다 뛰어다니는데, 원하는 때에 방향을 바꿀 수는 없다. 한 걸음은 언제나 동서남북 가운데 한 방향으로 곧게 나아간다.

운동장은 가로 $M$칸, 세로 $N$칸짜리 격자다. 위치는 $0 \le x < M$, $0 \le y < N$을 만족하는 좌표 $(x, y)$로 나타내며, $(0, 0)$이 왼쪽 아래 모서리다. N으로 한 걸음 옮기면 $y$가 1 커지고, S면 $y$가 1 작아지고, E면 $x$가 1 커지고, W면 $x$가 1 작아진다.

규칙은 다음과 같다.

• 놀이를 시작하기 전에 아이 한 명을 술래로 정한다.
• 놀이는 정해진 라운드 수만큼 진행하고, 한 라운드마다 모든 참가자가 자기가 보고 있는 방향으로 정확히 한 걸음씩 동시에 움직인다.
• 다음 걸음이 운동장 밖으로 나가는 참가자는 걸음을 내딛기 전에 방향을 반대로 돌린다. N과 S가 서로 반대이고, E와 W가 서로 반대다.
• 모두 한 걸음을 옮긴 뒤 두 명 이상이 서 있는 칸을 살핀다. 한 칸에 세 명 이상이 모이면 모두 방향을 반대로 돌린다. 한 칸에 정확히 두 명이 모이면 이렇게 방향을 주고받는다. 이름이 긴 쪽은 상대가 방금 움직인 방향을 보고, 이름이 짧은 쪽은 이름이 긴 쪽이 방금 움직인 방향의 반대를 본다. 두 방향 모두 방금 끝난 걸음에서 쓴 방향을 기준으로 정한다. 동네 아이의 이름 길이가 서로 다르기 때문에 이 규칙이 성립한다.
• 마지막 라운드가 끝나면 술래를 제외한 참가자 가운데 술래까지 직선 거리가 가장 짧은 사람이 이긴다. 거리가 같으면 이름이 짧은 쪽이 이긴다.

존은 시작 배치만 보면 결과가 이미 정해진다는 이유로 이 놀이를 시시하게 여긴다. 다른 아이에게 결과를 보여 주고 더 나은 놀이를 하자고 설득하려 한다. 존을 대신해 승자를 구하는 프로그램을 작성하자.

아래 그림은 첫 번째 예제 놀이의 시작 배치다.

첫 줄에 놀이의 수 $T$가 주어진다. 각 놀이는 다음 형식으로 주어진다.

놀이의 첫 줄에는 정수 $M$, $N$, $P$가 주어진다. 차례대로 운동장의 가로 길이, 세로 길이(둘 다 칸 수), 참가자 수다.

다음 $P$개 줄에는 참가자의 이름, 시작 칸의 $x$ 좌표와 $y$ 좌표, 처음에 보고 있는 방향이 공백으로 구분되어 주어진다. 방향은 N, S, E, W 중 하나다. 같은 칸에서 시작하는 참가자는 없으며, 가장 먼저 나오는 참가자가 술래다.

놀이의 마지막 줄에는 라운드 수 $R$이 주어진다.

제한은 다음과 같다.

• $1 \le T \le 100$
• $2 \le M \le 9$, $2 \le N \le 9$
• $2 \le P \le 9$이고 $P \le M \times N$
• $0 \le x < M$, $0 \le y < N$
• $1 \le R \le 1000$
• 이름은 알파벳 1자 이상 20자 이하이고, 한 놀이 안에서 이름 길이가 같은 참가자는 없다.

각 놀이마다 Case x: 이름 형식으로 한 줄씩 출력한다. $x$는 1부터 세는 놀이 번호이고, 이름 자리에는 이긴 참가자의 이름을 적는다.