Potaje de letras P65859

Un potaje de letras es como una sopa de letras, pero donde las palabras no tienen porqué aparecer únicamente en orden horizontal o vertical: las palabras son como spaghettis que pueden cambiar de orientación (vertical o horizontal) tantas veces como haga falta mientras aparecen en el potaje. Por ejemplo, el siguiente potaje contiene las palabras oie (2 veces) y mississipi, que marcamos en mayúsculas:

E   w   a   P   z   a
I   a   x   I   S   S
O   a   x   M   S   I
z   O   z   I   S   x
a   I   E   a   a   z

Fíjate que la palabra OIE aparece dos veces, y que la palabra MISSISSIPI reutiliza la misma letra I del potaje para representar sus dos últimas Is.

Te pedimos que hagas un programa que sea capaz de, dado un potaje de letras y una lista de palabras, descubrir si las palabras aparecen o no aparecen en el potaje. También te pedimos que tu programa marque las palabras que encuentra.

Entrada

La primera línea de la entrada contiene la palabra BUSCA (decidir, para cada palabra, si aparece o no) o MARCA (además de decidirlo, marcar encima del potaje todas las apariciones de las palabras que encuentres).

La segunda línea de la entrada contiene los números N, M≤ 50 y de filas y columnas del potaje de letras, y viene seguida de la descripción del potaje, con N líneas de M letras minúsculas. Por último, una línea con el número K≤ 50 de palabras que se te pregunta, ninguna de las cuales contendrá más de 50 letras minúsculas, y las K palaras, una por línea.

Salida

Escribe K líneas diciendo, para cada palabra, si aparece o no aparece en el potaje de letras, siguiendo el formato de los ejemplos.

Además, si la entrada empezaba con la palabra MARCA, escribe el potaje de letras, marcando todas las letras que forman parte de alguna palabra en mayúsculas.

Puntuación

• Test1:  25 Puntos 

  Resolver entradas BUSCA donde ninguna palabra tiene más de 3 letras.

• Test2:  20 Puntos 

  Resolver entradas BUSCA y MARCA donde ninguna palabra tiene más de 5 letras.

• Test3:  40 Puntos 

  Resolver entradas BUSCA de cualquier tipo.

• Test4:  15 Puntos 

  Resolver entradas BUSCA y MARCA de cualquier tipo.