로봇 암호

부정행위자가 있다고 의심하는 한 출제자는 다른 심사위원에게 보내는 메시지를 모두 암호로 바꿔서 보낸다. 표준 암호 방식은 쓰지 않는다. 표준 방식은 전부 하나의 음모라고 믿기 때문이다. 대신 부정행위자는 프로그래밍 실력이 가장 떨어진다고 보고, 복호화하려면 프로그램을 짜야 하는 방식을 직접 만들었다.

출제자는 암호문과 함께 복호화 규칙도 보내 왔다. 심사위원이 모두 그 규칙을 구현하지는 못하니, 대신 복호화하는 프로그램을 작성하라.

복호화는 격자 위에서 로봇을 움직여서 한다. 로봇은 격자의 북서쪽 모서리 칸에서 남쪽을 보고 출발한다. 북쪽은 맨 위 행, 서쪽은 맨 왼쪽 열이므로 남쪽으로 한 칸 가면 행 번호가 1 늘어난다. 로봇이 받는 명령은 세 가지다.

• L: 로봇이 왼쪽으로 90도 돈다.
• R: 로봇이 오른쪽으로 90도 돈다.
• F: 로봇이 바라보는 방향으로 한 칸 간다. 그 칸이 격자 밖이면 움직이지 않고 제자리에서 180도 돈다.

명령은 명령줄 단위로 주어진다. 명령줄 하나가 명령집합이고, 명령집합은 명령을 늘어놓은 문자열이며 그 안에 반복문이 들어갈 수 있다. 반복문은 (명령집합)숫자 꼴로 쓰고, 숫자는 괄호 안 명령집합을 실행하는 횟수다. 반복문은 중첩할 수 있어서 긴 명령을 재귀적으로 만들 수 있다.

명령집합 ::= 명령단위+
명령단위 ::= 명령 | 반복문
반복문   ::= "(" 명령집합 ")" 숫자
명령     ::= R | L | F
숫자     ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

로봇은 명령줄을 주어진 순서대로 실행하며, 한 명령줄이 끝나도 위치와 방향을 그대로 유지한 채 다음 명령줄을 실행한다. 명령줄이 하나 끝날 때마다 로봇이 서 있는 칸의 문자를 읽는다. 명령줄마다 하나씩 읽은 문자를 순서대로 이어 붙이면 복호화된 문자열이 된다.

첫째 줄에 시나리오의 수 $T$가 주어진다. 각 시나리오의 첫 줄에는 격자의 너비 $W$와 높이 $H$가 공백 하나를 사이에 두고 주어진다. 이어서 $H$개의 줄에 각각 $W$개의 문자가 주어지고, 이것이 격자다. 격자 다음 줄에는 명령줄의 개수 $N$이 주어지며, 그 뒤로 로봇이 실행할 명령줄 $N$개가 주어진다.

• $0 < T \le 100$
• $0 < W \le 50$
• $0 < H \le 50$
• $0 < N \le 20$
• 명령줄의 길이는 50자 이하이고 위 문법을 따른다.
• 격자에 나오는 문자의 아스키 값은 32 이상 126 이하다. 격자 칸에 공백이 들어갈 수 있다.

각 시나리오마다 복호화된 문자열을 한 줄에 출력한다.