Robot Encryption#1204
შესვლა

Robot Encryption

1 წამი
64 მეგაბაიტი
ძალიან რთული

Due to suspicions of cheating, one of the more paranoid problem setters decided to encrypt all his messages before sending them to the other jury members. He did not use any standard encryption methods, believing that they were all part of a conspiracy to undermine the IDI Open from within. He also believed that cheaters were the worst programmers, and since decryption required certain programming skills, it would be safe.

Along with each encrypted message, he sent information describing how to decrypt it. However, not all jury members were able to implement the decryption. You are to help decrypt the messages by writing a program to process them.

Decryption is performed by simulating the movement of a robot on a grid. Initially, the robot is placed in the north-west corner of the grid, facing south. The robot is a simple mechanism and can only execute three different commands:

  1. L turns the robot 90° to the left

  2. R turns the robot 90° to the right

  3. F moves the robot one cell forward. If moving forward would cause the robot to fall off the grid, it instead makes a 180° turn and does not move.

The robot's instructions are given as command sets, which may contain loops. A loop is written as (commandset)number, where number is the number of times to repeat the command set inside the parentheses. Long sequences of commands can be formed recursively in this way. More formally:

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

The decrypted text is obtained by concatenating the characters from the cells on which the robot stands after executing each command line.

შემავალი მონაცემები

The first line contains the number of test cases (0 < T \leq 100). Each test case starts with a line containing (0 < W \leq 50) and (0 < H \leq 50), separated by a single space, which define the grid's dimensions. This is followed by lines, each containing characters, describing the grid. The next line contains the number of command lines (0 < N \leq 20). After that, command lines follow, each to be executed by the robot.

Each command line contains at most characters and follows the syntax described above. No character with ASCII code less than or greater than will appear on the robot's grid.

გამომავალი მონაცემები

For each test case, output the decrypted text on a separate line.

მაგალითები

მაგალითი 1

Loading
Loading