#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/* For debug only: assertion macro for verifying input data */
#define ASSERT(e) { if(!(e)) throw #e; }

/* Maximum number of columns in crossword puzzle */
#define MAXCOLS 40

/* Maximum number of rows in crossword puzzle */
#define MAXROWS 40

/* A temporary array used when reading input and producing formatted output */
char puzzle[MAXCOLS][MAXROWS];

/* Size of the current puzzle as read in from the input */
int row_size, col_size;

/* Representation of a blank word space in the puzzle */
class edge;
class blank {
    public:
        int row, col;    /* Start position within puzzle[] for this blank */
        int length;      /* Length of the blank space */
        bool vert;       /* True = vertical; false = horizontal */
        string *word;    /* Word tentatively assigned to this space */
        vector<edge> edges; /* Other word spaces intersecting this one */

        /* Constructor used in parse_input() */
        blank(int r, int c, int l, bool b) : row(r), col(c), 
            length(l), vert(b), word(NULL) {}
};

/* A constraint representing the intersection of two word spaces */
class edge {
    public:
        int selfpos;    /* Intersection position within this word space */
        int otherpos;   /* Intersection position within other word space */
        blank *other;   /* The other word space we intersect with */
        
        /* Constructor required by vector<edge> */
        edge(void) : selfpos(0), otherpos(0), other(NULL) {}

        /* Constructor used in find_constraints() */
        edge(int sp, int op, blank &o) : selfpos(sp), otherpos(op), other(&o) {}
};

/* Predicate functions used with the find_if() STL algorithm */
bool pred_horiz(blank const &b) {
    return !b.vert;
}
bool pred_vert(blank const &b) {
    return b.vert;
}

/* List of puzzle blanks discovered from parsing the input */
vector<blank> blanks;

/* Holds the complete lists of words for a data set */
vector<string> words;

/* Used by solve() to keep track of which words are currently allocated */
vector<bool> usedwords;

/*
 * Read in one data set. First we read in the puzzle into the puzzle[] array
 * which makes it easier to analyze, and we read in the entire word list.
 * Second, we loop over puzzle[], detect the locations of all word spaces, and
 * fill in the blanks[] vector.
 */
void parse_input(void)
{
    int row, col, count, i;

    /* Iterate over all rows and columns and read input into puzzle[] array */
    for(row = 0; row < row_size; row++) {
        for(col = 0; col < col_size; col++) {
            char &c = puzzle[row][col];
            cin >> c;
            ASSERT(c == '#' || c == '.');
        }
    }

    /* Get the number of words in the input */
    cin >> count;
    
    /* Read in the word list */
    for(i = 0; i < count; i++) {
        string s;
        cin >> s;
        ASSERT(s.size() >= 2);
        words.push_back(s);
    }
    
    /* The usedwords flag vector must be same size as words list */
    usedwords.resize(words.size());

    /* Scan across rows looking for horizontal blanks */
    for(row = 0; row < row_size; row++) {
        for(col = 0; col < col_size; col++) {
            int start = col;

            /* Loop over # signs; two or more is a word space */
            while(puzzle[row][col] == '#' && col < col_size) {
                col++;
            }
            if(col - start >= 2) {
                blanks.push_back( blank(row, start, col - start, false) );
            }
        }    
    }

    /* Scan across columns looking for vertical blanks */
    for(col = 0; col < col_size; col++) {
        for(row = 0; row < row_size; row++) {
            int start = row;

            /* Loop over # signs; two or more is a word space */
            while(puzzle[row][col] == '#' && row < row_size) {
                row++;
            }
            if(row - start >= 2) {
                blanks.push_back( blank(start, col, row - start, true) );
            }
        }    
    }

    ASSERT(words.size() >= 1 && words.size() <= 100);
}

/*
 * Once the puzzle is solved, all blanks[].word fields are filled in with the
 * appropriate strings. This function iterates over blanks[], lays out
 * the assigned words within the puzzle[] char array, and then prints puzzle[]
 * on stdout.
 */
void print_puzzle(void)
{
    int row, col;

    /* Fill in the puzzle[] array with actual words allocations in blanks[] */
    for(int i = 0; i < blanks.size(); i++) {
        blank &b = blanks[i];        
        ASSERT(b.word);
        
        /* Fill in vertical blanks */
        if(b.vert) {
            for(int j = 0; j < b.length; j++) {
                puzzle[b.row + j][b.col] = (*b.word)[j];
            }
        }

        /* Fill in horizontal blanks */
        else {
            for(int j = 0; j < b.length; j++) {
                puzzle[b.row][b.col + j] = (*b.word)[j];
            }
        }
    }

    /* Print out the filled in puzzle[] array */    
    for(row = 0; row < row_size; row++) {
        for(col = 0; col < col_size; col++) {
            cout << puzzle[row][col];
        }
        cout << endl;
    }
}

/*
 * Scan through the blanks and find all intersections between horizontal and
 * vertical blanks. Precomputing all constraints avoids wasting any time during
 * the recursive backtracking search. This runs in O(N^2) time by checking each
 * word space against all other word spaces.
 */
void find_constraints(void)
{
    vector<blank>::iterator i = blanks.begin();
    
    /* Loop over all horizontal word spaces */    
    for(; (i = find_if(i, blanks.end(), pred_horiz)) != blanks.end(); ++i) {
        vector<blank>::iterator j = blanks.begin();

        /* Loop over all vertical words spaces */
        for(; (j = find_if(j, blanks.end(), pred_vert) ) != blanks.end(); ++j) {
        
            /* Skip if words don't overlap horizontally */
            if(j->col < i->col || j->col >= i->col + i->length) {
                continue;
            }
            
            /* Skip if words don't overlap vertically */
            if(i->row < j->row || i->row >= j->row + j->length) {
                continue;
            }
            
            /* Record the intersection offset within both word spaces */
            i->edges.push_back(edge(j->col - i->col, i->row - j->row, *j));
            j->edges.push_back(edge(i->row - j->row, j->col - i->col, *i));
        }
    }
}

/*
 * Check if the candidate "word" for the blank space "b" satisfies all
 * constraints between "b" and all other spaces it intersects (assuming those
 * spaces already have a tentative word allocated to them).  Returns true if
 * all constraints are satisfied.
 */
bool check_constraints(string &word, blank *b)
{
    /* Loop over all constraints */
    for(int i = 0; i < b->edges.size(); i++) {
        edge &e = b->edges[i];
    
        /* Return false if "word" does not meet this constraint */
        if(e.other->word && word[e.selfpos] != (*e.other->word)[e.otherpos]) {
            return false;
        }
    }
    
    /* Return true if "word" meets all constraints */
    return true;
}

/*
 * Called from solve() to find the next empty blank that will be assigned.
 * Optimization: we find the next empty blank that intersects with the most
 * other already assigned blanks. This reduces the number of possible
 * assignments allowed to this blank, and therefore reduces the total search
 * space.
 */
blank *next_blank(void)
{
    vector<blank>::iterator b;
    blank *candidate = NULL;
    int max = 0;

    /* Search through all blanks for the best one to assign next */    
    for(b = blanks.begin(); b != blanks.end(); ++b) {

        /* Only consider blanks not yet assigned a word */
        if(b->word == NULL) {
            vector<edge>::iterator e;
            int count = 0;
                  
            /* Count how many other assigned blanks this one intersects with */
            for(e = b->edges.begin(); e != b->edges.end(); ++e) {
                if(e->other->word) {
                    count++;
                }
            }

            /* Look for blank that intersects the most others */
            if(count >= max) {
                candidate = &(*b);
                max = count;
            }
        }
    }
    
    ASSERT(candidate);
    return candidate;
}

/*
 * Solve the crossword puzzle using a recursive backtracking search. Count is
 * an index into blanks[] and keeps track of which blank space will be assigned
 * next. If count reaches blanks.size(), then all the blanks were successfuly
 * filled in and the puzzle was solved. This runs in O(N!) since we explore all
 * permutations of N choose N.
 *
 * While searching for a solution, the usedwords[] (which corresponds one to
 * one with words[]) keeps track of which words have already been assigned. As
 * solve() recursively descends, it sets elements in usedwords[] to true as
 * the words are allocated. When backtracking, it sets them back to false so
 * those words can be reused again in another part of the search.
 *
 * While descending, blanks[].word is set to the tentative word being assigned
 * to this blank. When backtracking, blanks[].word is set back to NULL.
 *
 * Returns true if the puzzle was solved. Note that after finding a solution
 * this function keeps searching to verify that only one solution exists
 * and to measure the program's maximum running time.
 *
 * Optimization: We always try to assign the longest blank first, since
 * assigning the longest blank early on tends to impose the most constraints
 * on later assignments. This in turn helps to reduce the search space.
 */
bool solve(int count)
{
    bool result = false;

    /* If all blanks are allocated then the crossword is solved */
    if(count == blanks.size()) {
        print_puzzle();
        return true;
    }

    /* Find the next blank to assign */
    blank *b = next_blank();

    /* Attempt to allocate an unused word from word list to blanks[pos] */
    for(int i = 0; i < words.size(); i++) {
    
        /* Skip words currently allocated by solve()s above us */
        if(usedwords[i]) {
            continue;
        }

        /* Skip words that will not fit in the current blank space */
        if(words[i].size() != b->length) {
            continue;
        }
        
        /* Skip words that do not satisfy all constraints of this blank */
        if(!check_constraints(words[i], b)) {
            continue;
        } 
        
        /* Tentatively allocate current word into blank */
        b->word = &words[i];
        usedwords[i] = true;

        /* Recursively solve the rest of the puzzle with current assignment */
        result |= solve(count + 1);

        /* Deallocate the word from this blank so we can use it again */
        b->word = NULL;
        usedwords[i] = false;
    }
    
    /* Backtrack; crossword cannot be solved with current allocations */
    return result;
}

/* Main body of program */
void process(void)
{
    int puzzle_num, puzzle_idx;
    
    /* Read how many puzzles are to be analyzed */
    cin >> puzzle_num;

    /* Process each puzzle separately */
    for(puzzle_idx = 0; puzzle_idx < puzzle_num; puzzle_idx++) {
    
	/* Read in the puzzle size */
	cin >> col_size >> row_size;
        ASSERT(col_size >= 2 && col_size <= MAXCOLS)
        ASSERT(row_size >= 2 && row_size <= MAXROWS);
        
        /* Read in the puzzle and word list */
        parse_input();
        
        /* Find all word space intersections in puzzle */
        find_constraints();
        
        /* A crossword is only solvable if every word is used */
        cout << "Puzzle #" << puzzle_idx + 1 << endl;
        if(words.size() != blanks.size() || !solve(0)) {
            cout << "I cannot generate this puzzle." << endl;
        }

        /* Clear out all lists in preparation for next data set */
        words.clear();
        blanks.clear();
        usedwords.clear();
    }    
}

/* Run program and print out any exceptions that occur */
int main(void)
{
    /* Throw exceptions on EOF or failed data extraction in >> operator */
    cin.exceptions(ios::eofbit | ios::failbit);

    /* Run main body of code */
    try {
        process();
    }
    
    /* Catch any internally generated exceptions */
    catch(char const *e) {
        cerr << "Exception: " << e << endl;
    }
    
    /* Catch unexpected EOF or bad input data */
    catch(ios::failure const &e) {
        cerr << "Unexpected EOF or data type mismatch on input" << endl;
    }

    return 0;
}