Se trata de resolver el típico pasatiempo de "sopa de letras", pero con una ayuda importante: el programa conocerá de antemano qué palabras tiene que buscar.

Objetivo

Dada una tabla de letras con x filas e y columnas, se trata de buscar en ella diversas palabras que pueden aparecer escritas en horizontal (de izquierda a derecha, o de derecha a izquierda), en vertical (de arriba a abajo, o de abajo a arriba), o en diagonal (en cualquiera de las cuatro direcciones diagonales posibles). Se sabe además que cada palabra sólo aparecerá una vez en el tablero.

Entrada

La entrada del programa consiste de una secuencia de líneas, que residen en un archivo de texto (ASCII) con nombre SOP.DAT, que contendrá una serie de líneas:

• La primera línea contiene la dimensión del tablero, es decir, el número de filas (x) y columnas (y) del tablero (separados por un único espacio en blanco), cumpliéndose 0 <= x < 100, 0 <= y < 100.
• Las x siguientes líneas contienen en orden las x filas del tablero de letras. Cada una de estas líneas contiene (sin espacios en blanco) las y letras de la fila correspondiente.
• La siguiente línea del archivo (la x+2) contiene el número de palabras (n) que habrá que buscar en el tablero, cumpliéndose 0 <= n < 100.
• Y las n siguientes (y últimas) líneas del archivo contienen las n palabras que hay que encontrar. No habrá palabras de más de 20 letras.

A efectos de numeración, debe considerarse que las filas van de 1 a x y las columnas de 1 a y. Todas las letras, tanto del tablero como de las palabras, serán letras mayúsculas del alfabeto anglosajón (es decir, sin 'Ñ' ni 'Ç' y con 'W') sin acentos.

Salida

La salida del programa ha de grabarse en un archivo de texto (ASCII) con nombre SOP.RES, que contendrá exactamente n líneas, es decir, una línea por cada palabra buscada. En cada una de ellas se indicará la posición donde se halla la palabra correspondiente del archivo de entrada. Para indicar la posición de una palabra se darán las coordenadas (fila, columna) de su primera y su última letra (necesariamente en este orden). Estos cuatro valores irán separados sólo por espacios en blanco (un único espacio entre cada dos valores). Si alguna palabra no aparece en el tablero se escribirán tres interrogantes en la línea correspondiente.

Ejemplo de entrada

6 5
DOFGO
BARCO
OLUZA
TCTIA
ENAPX
YATES
14
AZUL
ZULO
LUZ
RUTA
DRAGON
OCA
TACO
CUCO
YATES
BARCO
BOTE
ANCLA
SETA
PAN

Ejemplo de salida

3 5 3 2
3 4 3 1
3 2 3 4
2 3 5 3
???
3 1 5 3
???
4 2 1 5
6 1 6 5
2 1 2 5
2 1 5 1
6 2 2 2
6 5 6 2
5 4 5 2