En un tablero de \(m \times n\) letras, una palabra aparece si se puede formar recorriendo celdas vecinas (arriba, abajo, izquierda o derecha), sin usar una misma celda más de una vez. Para cada palabra de la lista, di si aparece en el tablero.

Seguimiento: ¿puedes podar la búsqueda para que siga siendo rápida con tableros más grandes?

Entrada

La primera línea tiene \(m\) y \(n\) \((1 \le m, n \le 6)\) y siguen \(m\) líneas con \(n\) letras inglesas (mayúsculas o minúsculas) cada una. Luego viene \(k\) \((1 \le k \le 100)\) y \(k\) palabras de entre \(1\) y \(15\) letras, una por línea.

Salida

Para cada palabra, true si aparece o false si no.

Ejemplo 1

Entrada

3 4
ABCE
SFCS
ADEE
3
ABCCED
SEE
ABCB

Salida

true
true
false

Ejemplo 2

Entrada

1 1
a
2
a
ab

Salida

true
false

Basado en el problema 79 de LeetCode, Word Search, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.