Problem E: Juego de letras
Time Limit: 5 seconds

Description

Seguramente estás familiarizado con el juego de letras que consiste en buscar palabras en un mapa de letras. Las palabras pueden estar en horizontal, vertical o en diagonal. Sin embargo este juego de letras es distinto a los demás, como se puede observar en los siguientes ejemplos:

 

 

 

1

2

3

4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3

4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

2

 

 

 

4

3

2

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4

3

 

1

2

3

4

 

 

 

 

 

 

4

3

2

1

 

 

 

 

 

 

 

 

 

 

 

3

 

 

 

 

4

 

 

 

 

 

 

 

 

1

 

 

 

 

2

 

 

 

 

3

 

 

 

 

4

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

 

 

 

2

 

 

2

 

 

 

 

1

 

 

 

 

 

 

 

 

4

 

 

 

 

3

 

 

 

2

 

 

 

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

 

 

 

3

 

1

 

4

 

 

2

 

3

 

 

3

 

2

 

 

4

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4

 

 

 

 

2

 

 

 

 

1

3

 

 

 

 

 

 

1

3

 

 

 

 

2

 

 

 

 

 

 

 

 

 

 

4

 

 

 

 

 

 

3

 

 

 

 

 

2

 

 

 

 

 

1

 

 

 

 

4

 

 

 

 

 

 

 

 

 

4

 

 

 

 

 

 

 

 

 

 

2

 

 

 

 

3

1

 

 

 

 

1

 

 

 

4

 

2

 

 

 

3

 

3

 

 

 

2

 

4

 

 

 

1

 

4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

 

 

 

1

3

 

 

 

 

 

 

 

 

 

2

 

 

 

1

 

 

 

 

4

 

 

 

3

 

 

3

1

 

 

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4

 

4

1

 

 

 

2

 

 

 

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4

 

 

 

1

 

3

 

 

 

2

 

2

 

 

 

3

 

1

 

 

 

4

 

 

En este mapa los bordes no son limitantes. Ya que siempre existe una forma de continuar con el anagrama, tal y como se muestran en los ejemplos anteriores donde se ilustran todas las formas en que se puede formar la cadena ‘1234’ o ‘4321’ como lo quieras ver.

Dado un mapa de n x n (2 < n < 501) caracteres alfanuméricos y m (0 < m < 31) palabras a buscar, imprime el valor decimal del número binario de m digitos Bm Bm-1 … B1, donde Bi = 0 (0 < i <= m) si la i-ésima palabra no puede ser encontrada en el anagrama y Bi = 1 en caso contrario. Puedes estar seguro que todas las letras que conforman al mapa y a las palabras a buscar son todas minúsculas.

Input

La entrada consiste de varios casos de prueba. La primera línea de cada caso consiste de los valores de n y m, luego le siguen n líneas con un mapa de n x n caracteres, y al final una lista de m palabras (cada una de ellas en una línea diferente). La entrada termina con un caso m = n = 0, este último caso no debe producir salida alguna.

Output

Por cada caso imprime una línea con el número decimal formado a partir de las palabras que fueron o no encontradas en el anagrama. Lee la descripción para más detalle.

Sample input

Sample output

3 4
hol
aod
num
hola
mundo
nolu
cara
0 0
7


Problemsetter: Gabriel Filiberto López Pérez