Word Puzzle

Solve a word puzzle: find several words hidden in a rectangular grid.

Each word appears along one of the 8 directions (up, down, left, right, and the four diagonals) as a run of consecutive cells. For each word, determine the cell where it starts and the direction in which it is read from that cell.

The top-left cell has coordinates $(0, 0)$. The row number increases downward and the column number increases to the right.

Directions are labeled A through H, starting from North and going clockwise.

The first line contains the number of rows $L$, the number of columns $C$, and the number of words to find $W$ ($0 < L, C, W \le 1000$).

The next $L$ lines describe the grid; each line consists of $C$ uppercase letters.

The following $W$ lines each contain one word to find. Every word consists of uppercase letters and is guaranteed to appear in the grid.

Print the answer for each word on its own line, over $W$ lines. Each line contains the starting cell's row number, its column number, and a single letter (A~H) giving the reading direction, separated by spaces.

A word may appear in more than one place. In that case, apply the following rules in order and print only the single earliest match:

• smaller row number first;
• if the row numbers are equal, smaller column number;
• if both the row and column numbers are equal, smaller direction letter (A is smallest, H is largest).