// Steve Lagree
// CSE40872
// This program can solve a word search puzzle given the number of puzzles, dimensions, puzzle, number of words, and the words

#include <iostream>
#include <cctype>

using namespace std;

//compares characters ignoring case
int charCompare(char a, char b){
	if(tolower(a)==tolower(b)){
		return 1;
	}

	return 0;
}

//reads in the puzzle from stdin
void readPuzzle(string puzzle[], int rows,int cols){
	int i;
	for(i=0;i<rows;i++){
		getline(cin,puzzle[i]);
	}
}


//searches for a word given the location of the first letter and the direction to search in
int directionSearch(string puzzle[], int x, int y, int xDir, int yDir, string word,int row, int col){
	int letter=1;
	//cout << " First (" << y+1 << "," << x+1 << ")" << endl;
	x=x+xDir;
	y=y+yDir;
	
	//check boundaries
	while(x>=0&&y>=0&&x<col&&y<row){
		//cout << letter <<  " : (" << y+1 << "," << x+1 << ")" << endl;
		if(charCompare(puzzle[y][x],word[letter])==0){
	//		cout << "out\n";
			return 0;			
		}
		letter++;//increase the position of the letter in the word you are looking for
		x=x+xDir;//increase the x position in the right direction
		y=y+yDir;//increase y position in right direction
		if (letter==word.length()){ //if word is correct return 1
			return 1;
		}
	}
	//cout << "out\n";
	return 0;	//if word is not found, return 0

}

int searchWord(string puzzle[], string word,int row, int col,int &x, int &y,int &endx, int &endy){
	for(y=0;y<row;y++){ //look for first letter by going through each row and column
		for(x=0;x<col;x++){
			if(charCompare(puzzle[y][x],word[0])==1){ //once first letter is found call the directionSearch method
				if(directionSearch(puzzle,x,y,0,1,word,row,col)==1){ //up
					endx = x;
					endy = y+(word.length()-1)*1;
					return 1;
				}
				if(directionSearch(puzzle,x,y,0,-1,word,row,col)==1){ //down
					endx = x;
					endy = y+(word.length()-1)*-1;
					return 1;
				}
				if(directionSearch(puzzle,x,y,1,0,word,row,col)==1){//right
					endx = x+(word.length()-1)*1;
					endy = y+(word.length()-1)*0;
					return 1;
				}
				if(directionSearch(puzzle,x,y,-1,0,word,row,col)==1){ //left
					endx = x+(word.length()-1)*-1;
					endy = y+(word.length()-1)*0;
					return 1;
				}
				if(directionSearch(puzzle,x,y,-1,1,word,row,col)==1){ //up left
					endx = x+(word.length()-1)*-1;
					endy = y+(word.length()-1)*1;
					return 1;
				}
				if(directionSearch(puzzle,x,y,-1,-1,word,row,col)==1){ //down left
					endx = x+(word.length()-1)*-1;
					endy = y+(word.length()-1)*-1;
					return 1;
				}
				if(directionSearch(puzzle,x,y,1,-1,word,row,col)==1){ //down right
					endx = x+(word.length()-1)*1;
					endy = y+(word.length()-1)*-1;
					return 1;
				}
				if(directionSearch(puzzle,x,y,1,1,word,row,col)==1){ //up right
					endx = x+(word.length()-1)*1;
					endy = y+(word.length()-1)*1;
					return 1;
				}
			}
		}
	}
	return 0;	//if word isnt found, return 0

}

int main(){
	int numPuzzles,numWords,rows,cols,endx,endy,wordFound;
	int x=0;
	int y=0;
	cin >> numPuzzles; //read number of puzzles
	for(int i=0;i<numPuzzles;i++){
		if(i>0){
			cout << endl;
		}
		cout << "Map " << i+1 << endl;
		cin;
		cin >> rows >> cols; //read in puzzle dimensions
		string* puzzle;
		puzzle = new string[rows]; 
		cin.ignore();
		readPuzzle(puzzle,rows,cols); //read puzzle
		cin >> numWords;
		string* words;
		words = new string[numWords];
		for(int j=0;j<numWords;j++){ //read words
			cin >> words[j];
		}
		for(int j=0;j<numWords;j++){  //for each word search through puzzle
			wordFound=0;
			wordFound=searchWord(puzzle, words[j], rows, cols,x, y,endx, endy); //search for a word
			if(wordFound==1){ //if word is found, print out start and end location
				cout << words[j] << " (" << y+1 << ", " << x+1 << ") (" << endy+1 << ", " << endx+1 << ")" << endl;
			}
			else if(wordFound==0){ //otherwise print that it is not found
				cout << words[j] << " Not Found" << endl;
			}
		}
		delete [] puzzle;
		delete [] words;
	}


   return 0;
}