Word Puzzle

Did you heard of a little game named "Word Puzzle" ? If you didn't, what a pity !
In the game, you will be given a rectangular grid of letters, in which several words are hidden. Each word may begin anywhere in the puzzle, and may be oriented in any straight line horizontally, vertically, or diagonally. However, the words must all go down, right, or down-right. A dictionary is also given to you, indicating the words to be found in the grid.

You task is to find the locations of each word within the grid.

There is only one test case.

The first line is two integers R and C separated by a whitespace. R (20 ≤ R ≤ 500) is the number of rows of the grid. C (20 ≤ C ≤ 500) is the number of columns of the grid.

The following R lines, each line will contains exactly C characters without anything else. Each character is in the range 'A' - 'Z'.

A blank line will be followed after the grid.

The following lines, each line contains a unique word in the dictionary. Each word will contain between 1 and 20 characters ( also in the range 'A' - 'Z'). The dictionary consists of at most 10000 words.

-1 means the end of dictionary.

For each word, output the "ROW COL"(quotes for clarity) pair, where ROW is the 0-based row in which the first letter of the word is found, and COL is the 0-based column in which the first letter of the word is found. If the same word can be found more than once, the location in the lowest-indexed row should be returned. If there is still a tie, return the location with the lowest-indexed column. If a word cannot be found in the grid, return "-1 -1" for the word.

3 5
HENRY
GAVIN
MAGIC

HENRY
HGM
HAG
MAVIN
-1

0 0
0 0
0 0
-1 -1

XrtGavin@TJU

HDU 2007 Programming Contest - Final