#!/usr/bin/env python

# NPC Town
# Phil Bordelon

import os
import sys

DEBUG = os.getenv("DEBUG", False)

# Something useful for this program is a set of deltas for the directions.
DIR_DELTAS = {
"NORTH":  (-1, 0),
"SOUTH":  (1, 0),
"WEST":  (0, -1),
"EAST":  (0, 1)}

# As usual, we use classes as structures.
class Struct(object):
   pass

###
# printMap prints a map of the town given the current locations of NPCs.
def printMap(town):

   # Get all NPC locations and store them in a dictionary.
   npc_location_dict = {}
   for npc_letter in town.npc_dict:
      location = town.npc_dict[npc_letter].location
      npc_location_dict[location] = npc_letter

   for i in range(len(town.map)):
      to_print = ""
      for j in range(len(town.map[0])):
         if (i, j) in npc_location_dict:
            
            # An NPC.
            to_print += npc_location_dict[(i, j)]
         elif town.map[i][j].open:
            to_print += "."
         else:
            to_print += "#"
      print to_print

####
# processNPCScripts goes through the NPC scripts and fixes them up to be
# valid.
def processNPCScripts(town):

   for npc in town.npc_dict:

      # Let's get the starting location and script out first.
      start = town.npc_dict[npc].location
      script = town.npc_dict[npc].script

      current_location = start
      # We're going to build a revised script that breaks all steps down
      # into single units: move one square, pause one unit.
      new_script = []
      for script_step in script:
         command, count = script_step.split()
         count = int(count)
         for count_loop in range(count):
            if command in DIR_DELTAS:

               # It's a direction.  Let's see if this puts us out of bounds.
               move_i = current_location[0] + DIR_DELTAS[command][0]
               move_j = current_location[1] + DIR_DELTAS[command][1]

               if (move_i >= 0 and move_i < town.height and move_j >= 0
                and move_j < town.width and town.map[move_i][move_j].open):
                  
                  # This is a valid move; it doesn't go off the map or into
                  # a non-open space.  Add it to the new script.
                  new_script.append(command)

                  # Move to that location.
                  current_location = (move_i, move_j)

               else:

                  # Invalid move.  Make it a pause.
                  new_script.append("PAUSE")
            elif command == "PAUSE":
               new_script.append("PAUSE")
            else:
               print("ERROR: Unknown command type in script!")
               sys.exit(4)

      # Now that we have a broken-down script, let's see if we ended back
      # where we started.  If so, we're done.  If not, we have to append
      # a reversed copy of the script.
      if current_location != start:

         # Drat.  Time to add a reversed copy.
         reversed = new_script[:]
         reversed.reverse()
         for i in range(len(reversed)):
            if reversed[i] == "NORTH":
               reversed[i] = "SOUTH"
            elif reversed[i] == "SOUTH":
               reversed[i] = "NORTH"
            elif reversed[i] == "WEST":
               reversed[i] = "EAST"
            elif reversed[i] == "EAST":
               reversed[i] = "WEST"

         new_script.extend(reversed)

      # Lastly, replace the old script with the fixed one.
      town.npc_dict[npc].script = new_script

      if DEBUG:
         print("NPC %s's script:" % (npc))
         for command in town.npc_dict[npc].script:
            print(command)

####
# simulate "simulates" an amount of time passing in the town.
def simulate(town, step_count):

   # We are utterly cheating cheaters.  Simulating 1,000,000 steps is way
   # too much like work.  Instead, we use the fact that all scripts are,
   # in the end, repetitive; we can use modulus arithmetic to know which
   # step in the repetitive loop each NPC will be in.

   for npc_letter in town.npc_dict:

      npc = town.npc_dict[npc_letter]
      start = npc.location
      script_length = len(npc.script)

      # Okay.  So, what's the modulus?
      steps_to_simulate = step_count % script_length

      # Now, simulate that many steps.
      curr_loc = start
      for step in range(steps_to_simulate):
         if npc.script[step] in DIR_DELTAS:
            
            # We actually need to move for this step.
            delta = DIR_DELTAS[npc.script[step]]
            curr_loc = (curr_loc[0] + delta[0], curr_loc[1] + delta[1])

         # Else it's a PAUSE, in which case we do nothing.

      # All right, we're at our destination!  That was easy.
      npc.location = curr_loc

####
#
#
def main():
   dataset_count = int(sys.stdin.readline())

   for dataset_loop in range(dataset_count):

      print("DATA SET #%d" % (dataset_loop + 1))

      # A new town, a new beginning.
      town = Struct()

      town.npc_count = int(sys.stdin.readline())

      town.height, town.width = [int(x) for x in
       sys.stdin.readline().strip().split()]

      # Read in the town; when we come across NPCs, log 'em too.
      town.npc_dict = {}
      town.map = []
      for i in range(town.height):
         town_row = []
         town_line = sys.stdin.readline().strip()
         for j in range(town.width):

            loc = Struct()
            if town_line[j] == ".":
               loc.open = True
            elif town_line[j] == "#":
               loc.open = False
            else:

               # NPC.
               loc.open = True
               if town_line[j] in town.npc_dict:
                  print("ERROR: Duplicate NPC in this town!")
                  sys.exit(1)
               else:
                  npc = Struct()
                  npc.location = (i, j)
                  npc.script = None

                  town.npc_dict[town_line[j]] = npc

            town_row.append(loc)
         town.map.append(town_row)

      if DEBUG:
         printMap(town)

      # Read in the scripts ...
      for script_loop in range(town.npc_count):
         npc_letter, script_length = [x for x in
          sys.stdin.readline().strip().split()]
         script_length = int(script_length)

         if npc_letter not in town.npc_dict:
            print("ERROR: Mismatched NPC letter in script!")
            sys.exit(2)

         elif town.npc_dict[npc_letter].script:
            print("ERROR: Duplicate NPC script!")
            sys.exit(3)

         npc_script = []
         for steps_loop in range(script_length):
            npc_script.append(sys.stdin.readline().strip())

         town.npc_dict[npc_letter].script = npc_script

      # Now we need to process the NPC scripts.
      processNPCScripts(town)

      # Read the step count ...
      step_count = int(sys.stdin.readline())

      # And "simulate."
      simulate(town, step_count)

      # Finally, print out what the town looks like after that
      # many steps.
      printMap(town)


if "__main__" == __name__:
   main()