#include <ctype.h>
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
#include <string>
#include <map>

using namespace std;

/*
 * DEBUG ONLY: If compiled -DDEBUG, the program will show the transformed
 * scripts (on stderr) for each NPC that avoid collisions and are always
 * inherently cyclic. If compiled -DSTEP, the program will show the town state
 * (also on stderr) after every single turn. Note that using -DSTEP makes the
 * entire program too slow to actually finish running the master data sets.
 * With -DSTEP we no longer do the "modulo optimization" that takes advantage
 * of cyclic nature of the NPCs walk scripts.
 */

/* SANITY CHECK: assertion macro for verifying input data and internal state */
#define ASSERT(e) { if(!(e)) { cerr << #e << endl; throw; } }

/* Max width/height of a town */
#define MAXSIZE 40

/* Return the minimum of two values */
#define min(a,b) ((a) < (b) ? (a) : (b))

/* Generic integer pair used for several things in the program */
typedef pair<int, int> coord_t;

/* Dictionary to map verb names to indices into the VERB array */
map<string, int> NAMES;

/* DEBUG ONLY: Array mapping VERB array indices to string names for printing */
const char *PRINT[] = {
    "NORTH", "SOUTH", "EAST", "WEST", "PAUSE"
};

/* These are the "reversed" verb numbers for each of the commands in NAMES[] */
const int REVERSE[] = { 1, 0, 3, 2, 4 };

/*
 * The effect that each of the command verbs has on a NPC's position can be
 * encoded in terms of a row and column offset that's applied to the position
 * every turn. This array is in the same order as NAMES to facilitate easy
 * lookup. The offsets are of the form (row, col).
 */
const coord_t VERB[] = {
    coord_t(-1, 0), coord_t(1, 0), coord_t(0, 1), coord_t(0, -1), coord_t(0, 0)
};

/* Index into VERB[] for the pause command */
#define PAUSE 4

/*
 * A command is a (verb, value) pair where "verb" is an integer between 0 and 4
 * (matching the VERB[] array) and "value" is an integer indicating how far to
 * move or how long to pause for. The command map associates each command list
 * with the NPC single character id as read from the input data set.
 */
typedef vector<coord_t> cmdlist_t;
typedef map<char, cmdlist_t> cmdmap_t;

/* Maps an NPC char id (number or letter) to the NPC position as (row, col) */
typedef map<char, coord_t> npcmap_t;

/*
 * The array is used to hold the town layout but only for tracking the
 * open vs wall spaces. Actual NPC locations are only stored in a datalist_t
 * object since that's an easier format to update as the NPCs move around.
 */
typedef char grid_t[MAXSIZE][MAXSIZE];

/*
 * Print the town layout to the "out" stream and show the location of every
 * NPC in "npcmap" by printing the appropriate NPC character on top of the
 * layout.
 */
void output(ostream &out, grid_t grid, npcmap_t &npcmap, int width, int height)
{
    npcmap_t::iterator i;

    /* Temporarily add the NPCs to the grid for printing */
    for(i = npcmap.begin(); i != npcmap.end(); ++i) {
        grid[i->second.first][i->second.second] = i->first;
    }

    for(int row = 0; row < height; row++) {
        for(int col = 0; col < width; col++) {
            out << grid[row][col];
        }
        out << endl;
    }    

    /* Reset NPC locations back to empty spaces */
    for(i = npcmap.begin(); i != npcmap.end(); ++i) {
        grid[i->second.first][i->second.second] = '.';
    }
}

/*
 * DEBUG ONLY: Simulate one turn for a given NPC. The current command in
 * "cmdlist" (current as determined by "instptr") is executed and the NPC
 * position "pos" updated. Once the current command has finished executing,
 * the "instptr" is advanced (possibly wrapping around) to the next command.
 */ 
void simulate_one(grid_t grid, int width, int height, coord_t &instptr,
    cmdlist_t &cmdlist, coord_t &pos)
{
    int ip = instptr.first;
    
    /*
     * If NPC's command is finished, increment instruction pointer but skip
     * over any commands who had their delay value reduced to zero by fixup().
     */
    while(instptr.second == 0) {
        ip = (ip + 1) %  cmdlist.size();
        instptr.first = ip;
        instptr.second = cmdlist[ip].second;
    }

    /* Execute current command and decrement instruction delay */
    pos.first += VERB[cmdlist[ip].first].first;
    pos.second += VERB[cmdlist[ip].first].second;
    instptr.second--;
}

/*
 * DEBUG ONLY: Simulate one turn across all NPCs in the data set. The
 * "instptr" map holds "instruction pointers" for every NPC. Every
 * instruction pointer is a pair (cmdnum, delay) where "cmdnum" is an index
 * into cmdmap of the currently executing command and "delay" is the number
 * of turns remaining until the current command finishes executing.
 */
void simulate_all(grid_t grid, int width, int height, npcmap_t &instptr,
    cmdmap_t &cmdmap, npcmap_t &npcmap)
{
    npcmap_t::iterator i;

    /* Move each NPC by one turn */
    for(i = npcmap.begin(); i != npcmap.end(); ++i) {        
        char npc = i->first;
        
        simulate_one(grid, width, height, instptr[npc],
            cmdmap[npc], npcmap[npc]);
    }
}

/*
 * Execute a command "cmd" a single turn by updating the position of "oldpos" If
 * this command caused the NPC to hit a solid object or the edge of the map,
 * then return true and don't update "oldpos". Used by fixup() to detect
 * collisions in the script and to re-write the script accordingly.
 */
bool execute(coord_t cmd, coord_t &oldpos, grid_t grid, int width, int height)
{
    coord_t pos;

    pos.first = oldpos.first + VERB[cmd.first].first;
    pos.second = oldpos.second + VERB[cmd.first].second;

    if(pos.first < 0 || pos.second < 0 || pos.first >= height ||
        pos.second >= width || grid[pos.first][pos.second] != '.')
        return true;
    
    oldpos = pos;
    return false;
}

/*
 * Execute the "cmdlist" script one time through and if any collisions are
 * found, re-write it to a form that avoids the collisions all together by
 * inserting the appropriate number of PAUSEs. Also if the script is not
 * already inherently cyclic, make it so by appending a reversed version
 * of the collision-free script that will return the NPC to its original
 * location. Finally, this function computes the total cycle length (in turns)
 * of the NPC's walk script and returns it. The cycle length is used for
 * a modulo optimization later on.
 */
int fixup(grid_t grid, coord_t pos, int width, int height, cmdlist_t &cmdlist)
{
    cmdlist_t::iterator i;
    coord_t start = pos;
    
    /*
     * Execute through all the commands in the list and run each command for the
     * specified number of turns. If we hit a wall or edge, split this command
     * into a shortened original and a PAUSE for the remainder of the
     * "collision" time.
     */
    for(i = cmdlist.begin(); i != cmdlist.end(); ++i) {
        coord_t cmd = *i;
        
        for(int j = 0; j < cmd.second; j++) {
            if(execute(cmd, pos, grid, width, height)) {
                *i = coord_t(cmd.first, j);
                ++i;
                i = cmdlist.insert(i, coord_t(PAUSE, cmd.second - j));
                break;
            }
        }
    }
    
    /* If the script is reversible, make it cyclic */
    if(pos != start) {
        int size = cmdlist.size();
        cmdlist.resize(size * 2);
        
        /* Append a duplicated and reversed command list */
        copy(&cmdlist[0], &cmdlist[size], &cmdlist[size]);
        reverse(&cmdlist[size], &cmdlist[size * 2]);
        
        /* Reverse directions of individual commands in list */
        for(int i = size; i < size * 2; i++) {
            cmdlist[i].first = REVERSE[cmdlist[i].first];
        }
    }
    
    /* Calculate the total cycle length of the walk script */
    int total = 0;
    for(i = cmdlist.begin(); i != cmdlist.end(); ++i) {
        total += i->second;
    }
    return total;
}

/* Main body of program */
void process(void)
{
    int data_num, data_idx;

    /* Initialize the global NAMES[] dictionary */
    NAMES["NORTH"] = 0;
    NAMES["SOUTH"] = 1;
    NAMES["EAST"] = 2;
    NAMES["WEST"] = 3;
    NAMES["PAUSE"] = 4;
    
    /* Read how many data sets to process */
    cin >> data_num;
    
    /* Process each data set separately */
    for(data_idx = 0; data_idx < data_num; data_idx++) {   
        int npc_num, npc_idx;     /* For looping over command lists */
        int width, height, turns; /* Parameters from data set input */
        npcmap_t npcmap;          /* Tracks position of each NPC */
        npcmap_t instptr;         /* DEBUG ONLY: current command during sim */
        cmdmap_t cmdmap;          /* Command list per NPC */
        map<char, int> cycle;     /* Total walk cycle length per NPC */        
        grid_t grid;              /* Town layout */
        
        cin >> npc_num >> height >> width;
        ASSERT(1 <= npc_num && npc_num <= 35);
        ASSERT(1 <= height && height <= 40);
        ASSERT(1 <= width && width <= 40);
        
        /* Read in the town grid */
        for(int row = 0; row < height; row++) {
            for(int col = 0; col < width; col++) {
                char npc;
                
                cin >> npc;
                
                /* Numbers and letters are NPC locations; record in npcmap */
                if(isalnum(npc)) {
                    npcmap[npc] = coord_t(row, col);
                    grid[row][col] = '.';
                }
                
                /* Otherwise it's a wall or empty space; record in grid */
                else {
                    ASSERT(npc == '.' || npc == '#');
                    grid[row][col] = npc;
                }
            }
        }
        
#if defined(STEP) || defined(DEBUG)
        cerr << "DATA SET #" << data_idx + 1 << endl;
#endif        
        /* Read in the command scripts for each NPC */
        for(npc_idx = 0; npc_idx < npc_num; npc_idx++) {            
            int cmd_idx, cmd_num;
            char npc;

            /* Read NPC id and command count */
            cin >> npc >> cmd_num;
            ASSERT(npcmap.find(npc) != npcmap.end());
            ASSERT(1 <= cmd_num && cmd_num <= 20);
            
            /* DEBUG ONLY: Init "instruction pointer" used by simulate_all() */
            instptr[npc] = coord_t(-1, 0);

            /* Read the list of commands into cmdmap[npc] list */
            for(cmd_idx = 0; cmd_idx < cmd_num; cmd_idx++) {
                string word;
                int value;
                
                cin >> word >> value;
                ASSERT(NAMES.find(word) != NAMES.end());
                ASSERT(1 <= value <= 40);
                
                cmdmap[npc].push_back(coord_t(NAMES[word], value));
            }
            
            /* Detect collisions and make reversible walks cyclic */
            cycle[npc] = fixup(grid, npcmap[npc], width, height, cmdmap[npc]);
            
#if defined(STEP) || defined(DEBUG)
            /* DEBUG ONLY: Show transformed command list with no collisions */
            cerr << "Transformed script " << npc << ":" << endl;
            
            cmdlist_t::iterator i;
            for(i = cmdmap[npc].begin(); i != cmdmap[npc].end(); ++i) {
                cerr << PRINT[i->first] << " " << i->second << endl;
            }
            
            cerr << "Cycle length: " << cycle[npc] << endl << endl;
#endif
        }
        
        /* Read the number of turns to simulate for */
        cin >> turns;
        ASSERT(1 <= turns && turns <= 1000000);

#ifdef STEP
        /* DEBUG ONLY: Show initial grid layout before simulation */
        cerr << "Initial layout:" << endl;
        output(cerr, grid, npcmap, width, height);
        cerr << endl;

        /* DEBUG ONLY: Run a full simulation to show how NPCs move */
        for(int i = 0; i < turns; i++) {        
            simulate_all(grid, width, height, instptr, cmdmap, npcmap);
            
            cerr << "Turn " << i + 1 << ":" << endl;
            output(cerr, grid, npcmap, width, height);
            cerr << endl;
        }
#else
        /*
         * Because every NPC movement is cyclic, we can reduce the computation
         * time by separately simulating only "turns modulo cycle length" for
         * every NPC.
         */      
        for(npcmap_t::iterator i = npcmap.begin(); i != npcmap.end(); ++i) {
            int ip = 0;
            char npc = i->first;
            int npcturns = turns % cycle[npc];

            coord_t &pos = npcmap[npc];
            cmdlist_t &cmdlist = cmdmap[npc];
            
            /*
             * We can get a further optimization by executing a single command
             * per loop iteration and "scaling" the distance moved by the
             * command's "value".
             */
            while(npcturns) {                              
                int verb = cmdlist[ip].first;
                int value = min(npcturns, cmdlist[ip].second);

                /* Execute current command and decrement instruction delay */
                pos.first += VERB[verb].first * value;
                pos.second += VERB[verb].second * value;
                
                /* Advance to next instruction in command list */
                npcturns -= value;
                ip = (ip + 1) % cmdlist.size();
            }
        }
#endif     
        /* Show the final state of the town */
        cout << "DATA SET #" << data_idx + 1 << endl;
        output(cout, grid, npcmap, width, height);        
    }
} 


/* Run program and print out any exceptions that occur */
int main(void)
{
    /* Throw exceptions on failed data extraction in >> operator */
    cin.exceptions(ios::failbit);
    
    /* Run main body of code */
    try {
        process();
    }
    
    /* Catch unexpected EOF or bad input data */
    catch(ios::failure const &e) {
        cerr << "Unexpected EOF or data type mismatch on input" << endl;
    }

    return 0;
}