International Programming Contest

April 19, 2003, Blagoevgrad, Bulgaria

Sponsored by  

Task E. Words search


There is a matrix of letters. The object is to find a given word in the matrix. A word may be started anywhere in the table and proceeded diagonal, vertical or horizontal. Write a program E.EXE to solve the task.



The first line of input will specify the length (in characters) n (1<n<100) of the sides of the square letter matrix. The next n lines of input will be the matrix itself, each line will contain n uppercase letters. A list of words will follow. Each word will be on a line by itself; there will be 100 or fewer words. Each word will be 100 or fewer characters long, and will only contain uppercase letters. The final line of input will contain a single zero character.



Your program should find each word from the word list in the letter matrix. A word is "found'' if all the characters in the word can be traced in a single (unidirectional) horizontal, vertical, or diagonal line in the letter matrix. The horizontal and diagonal words may proceed from right to left;  the vertical and diagonal words - from bottom to top ("backwards''). For each word that is found, your program should print the coordinates of its first and last letters in the matrix on a single line, separated by a single space. Coordinates are pairs of comma-separated integers (indexed from 1), where the first integer specifies the row number and the second integer specifies the column number. If a word is not found, the string Not found should be output instead of a pair of coordinates.  Each word from the input can be "found'' at most once in the puzzle.


Sample Input



Sample Output

1,1 6,6
3,1 3,5
5,5 2,5
Not found