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.