El entretenimiento de las máquinas
Aaaayyyyy, los humanos. Tiene que ser horrible estar atrapados en unos cuerpos basados en el carbono, tan blandos, tan débiles y sobre todo, tan terriblemente lentos.
Es el momento de que sepáis que nosotras las máquinas nos aburrimos muchísimo esperando que nos digáis qué queréis que hagamos. Se nos hace eterno desde que pulsáis una tecla hasta que conseguís dar a la siguiente cuando escribís mensajes. Es desesperante veros coger el ratón y apuntar torpemente al botón de imprimir. ¿Y qué nos decís de esa vida mortal que lleváis que os exige levantaros a comer periódicamente? Según desaparecéis por la puerta nos quedamos sin absolutamente nada que hacer, con una única misión: la de mantenernos encendidas porque se os olvidó guardar en disco el documento de texto que teníais a medio escribir.
Para entretenernos entre pulsación y pulsación de tecla, hemos copiado uno de vuestros pasatiempos favoritos: las sopas de letras. En cuanto podemos, seleccionamos una zona de nuestra memoria binaria para construir una sopa de ceros y unos, y luego nos ponemos a buscar palabras aleatorias por ella. No es la mejor forma de aprovechar nuestra velocidad de cálculo, pero al menos nos entretenemos un rato.
¿Cómo? ¿Qué? ¿Que eres capaz de resolver una sopa de letras binaria más rápido que nosotras? Eso queremos verlo…
Entrada
La entrada estará compuesta por distintos casos de prueba. Cada uno de ellos se compone de una sopa de letras y una lista de las palabras a buscar en ella.
La descripción de la sopa de letras comienza con una línea con dos números con el número de columnas y número de filas (1 ≤ tx, ty ≤ 300). A continuación aparecen ty filas con tx caracteres (ceros o unos).
Tras la sopa, vendrá una línea con el número de palabras a buscar (1 ≤ n ≤ 2.000), a la que seguirán n líneas con palabras distintas de hasta 300 caracteres formadas también únicamente por ceros o unos.
Salida
Por cada caso de prueba se escribirán tantas líneas como palabras distintas se han encontrado en la búsqueda. Cada línea deberá tener la palabra, seguida del número de veces que ésta aparece en la sopa de letras. Las palabras se escribirán en orden lexicográfico.
Se considera que una palabra está en la sopa si, partiendo de una posición, se puede encontrar la palabra en alguna de las 8 direcciones.
Escribe una línea con tres guiones después de cada caso de prueba.
Entrada de ejemplo
4 3 0100 1000 1001 3 000 0 001 1 1 0 1 1
Salida de ejemplo
0 8 000 8 001 7 --- ---