Wandering Aimlessly

Many console role-playing games fill their towns with minor characters (NPCs) who wander around aimlessly, waiting for the player to talk to them. Your job is to implement the movement of these town NPCs for a new game.

Every NPC has a movement script made of a few simple commands:

The people who write these scripts are not always careful, so a script may tell an NPC to walk through a wall or off the edge of the map. Whenever that happens, every movement step that would put the NPC in an invalid cell is converted into a PAUSE. For example, given this small piece of a town:

...#
.1.#
...#

if the NPC marked 1 had EAST 5 as its next command, it would be converted on the fly into EAST 1 followed by PAUSE 4. This conversion must be done before deciding whether a script is cyclic or reversible.

A script is cyclic if, at the end of the script, the NPC is back on its starting cell; such a script is simply looped forever. Otherwise the script is reversible: if the NPC is not back on its starting cell at the end of the script, it then runs a reversed copy of the (already converted) script, with the directions switched (WEST becomes EAST, EAST becomes WEST, NORTH becomes SOUTH, and SOUTH becomes NORTH) and PAUSEs left intact. The end result is the character returning to its starting cell.

For this problem you may assume that no two NPCs ever try to occupy the same cell on the same turn, although one NPC may enter a cell on the same turn another one leaves it, which is valid.

The simulation starts at turn 0. Given a map and a set of NPCs with their scripts, report what the town looks like after a given number of turns have passed.

The input begins with a line containing a single integer N (1 ≤ N ≤ 100), the number of data sets. Each data set consists of the following parts:

• A line with a single integer C (1 ≤ C ≤ 35), the number of NPCs in this town.
• A line with two integers H and W (1 ≤ H, W ≤ 40), the height and width of the town.
• H lines describing the town, each with W characters:
  • # marks a wall or other impassable obstruction;
  • . marks an open space;
  • a digit or capital letter marks the starting cell of an NPC — 1 is the first NPC, 2 the second, and so on through 9, then A is the tenth, B the eleventh, and so on. The cell under an NPC's starting position counts as open.
• C blocks describing the NPC scripts. Each block consists of:
  • A line with a single character and an integer L (1 < L < 20), separated by a space, where the character is the map symbol of one NPC and L is the length of that NPC's script;
  • L lines giving that NPC's script in the format above, with no argument larger than 40.
• A line with a single integer T (1 ≤ T ≤ 1000000), the number of turns to simulate.

For each data set, print the heading DATA SET #k, where k is 1 for the first data set, 2 for the second, and so on. Then print H lines showing the town map, using the same symbols as the input, with every NPC drawn in the cell it occupies after the given number of turns have passed.