¿Dónde está Waldorf? X93339

Dado una cuadrícula de letras de tamaño m por n y una lista de palabras, encuentra la ubicación en la cuadrícula en la que la palabra puede ser encontrada.

Una palabra coincide con una línea recta e ininterrumpida de letras en la cuadrícula. Una palabra puede coincidir con las letras en la cuadrícula sin importar su mayúscula o minúscula (es decir, las letras en mayúscula y minúscula deben ser tratadas como iguales). La coincidencia puede hacerse en cualquiera de las ocho direcciones horizontales, verticales o diagonales a través de la cuadrícula.

Entrada

El input comienza con un único entero positivo en una línea por sí sola indicando el número de casos, seguido de una línea en blanco. También hay una línea en blanco entre cada dos casos consecutivos. Cada caso comienza con un par de enteros m seguido de n en una sola línea, donde 1 <= m, n <= 50 en notación decimal. Las siguientes m líneas contienen n letras cada una, representando la cuadrícula de letras donde se deben encontrar las palabras. Las letras en la cuadrícula pueden estar en mayúsculas o minúsculas. Después de la cuadrícula de letras, aparece otro entero k en una línea por sí sola (1 <= k <= 20). Las siguientes k líneas de entrada contienen la lista de palabras a buscar, una palabra por línea. Estas palabras pueden contener solo letras en mayúsculas y minúsculas, sin espacios, guiones u otros caracteres no alfabéticos.

Salida

Para cada palabra en cada caso de prueba, se debe generar un par de enteros que representen su ubicación en la cuadrícula correspondiente. Los enteros deben estar separados por un solo espacio. El primer entero es la línea en la cuadrícula donde se puede encontrar la primera letra de la palabra dada (1 representa la línea más alta en la cuadrícula, y m representa la línea más baja). El segundo entero es la columna en la cuadrícula donde se puede encontrar la primera letra de la palabra dada (1 representa la columna más a la izquierda en la cuadrícula, y n representa la columna más a la derecha en la cuadrícula). Si una palabra se puede encontrar más de una vez en la cuadrícula, se debe dar la ubicación de la ocurrencia más alta de la palabra (es decir, la ocurrencia que coloca la primera letra de la palabra más cerca de la parte superior de la cuadrícula). Si dos o más palabras están en la posición más alta, se debe dar la ubicación más a la izquierda de estas ocurrencias. Todas las palabras se pueden encontrar al menos una vez en la cuadrícula. La salida de dos casos consecutivos debe estar separada por una línea en blanco.