Robotic Encryption

A problem setter who suspects cheaters encrypts every message before sending it to the rest of the jury. He does not use a standard cipher, because he believes the standard ones are all part of one conspiracy. He assumes instead that a cheater is a weak programmer, so he built a scheme whose decryption needs a program.

He sent the decryption rules along with the encrypted message. Not every member of the jury can implement them, so write the program that does it.

Decryption simulates a robot moving on a grid. The robot starts in the north-west corner, facing south. North is the top row and west is the leftmost column, so a step to the south increases the row number by 1. The robot accepts three commands.

• L turns the robot 90 degrees to the left.
• R turns the robot 90 degrees to the right.
• F moves the robot one square forward. If moving forward would take the robot off the grid, the robot turns 180 degrees on the spot and does not move.

Commands arrive one commandline at a time. A commandline is a commandset, and a commandset is a string of commands that may contain loops. A loop is written as (commandset)number, where number is how many times the commandset inside the parentheses runs. Loops nest, so a long sequence of commands is built up recursively.

commandset  ::= instruction+
instruction ::= command | loop
loop        ::= "(" commandset ")" number
command     ::= R | L | F
number      ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

The robot runs the commandlines in the order given and keeps its position and its facing from one commandline to the next. Every time a commandline finishes, read the character on the square the robot stands on. Concatenating those characters, one per commandline, gives the decrypted text.

The first line holds $T$, the number of test scenarios. Each scenario starts with a line holding the width $W$ and the height $H$ of the grid, separated by one space. Then come $H$ lines of $W$ characters each, which make up the grid. After the grid comes a line holding $N$, the number of commandlines, followed by the $N$ commandlines the robot runs.

• $0 < T \le 100$
• $0 < W \le 50$
• $0 < H \le 50$
• $0 < N \le 20$
• A commandline is at most 50 characters long and follows the grammar above.
• Every character on the grid has an ASCII value between 32 and 126, so a grid square can hold a space.

For each test scenario print one line, the decrypted text.