C - Operador de multiplicación

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

Sea $C$ un alfabeto de cardinalidad $K$ y un operador $\rho$ de multiplicación de los elementos de $C$, $\rho: C × C → C$. Diseñe un algoritmo que dada una cadena $x = x_{1}x_{2} ... x_{n}$ sobre el alfabeto $C$ y un símbolo $a$ del alfabeto determine si es posible parentizar $x$ de forma tal que el resultado obtenido coincida con $a$. El operador de multiplicación $\rho$ no tiene que ser ni asociativo ni conmutativo.

Input

La primera línea de la entrada es un entero $K (1 \leq K \leq 26)$ la cantidad de letras en el alfabeto. Le siguen $K$ líneas, cada una con $K$ letras representando la matriz de multiplicación. Todas las letras en la matriz están entre las primeras $K$ letras del alfabeto latino. La siguiente fila es un entero $N (1 \leq N \leq 20)$ el tamaño de la cadena. Le sigue una fila con la cadena. La última fila es la letra que se quiere obtener. Todas las letras de la cadena, al igual que la que se quiere obtener, están entre las primeras $K$ letras del alfabeto latino.

Output

Si es posible parentizar la cadena de forma tal que el operador de multiplicación obtenga la letra buscada se debe imprimir $\texttt{“SI”}$. En caso contrario se debe imprimir $\texttt{“NO”}$.

Sample test(s)

Input
3 aba cbb aca 3 abc b
Output
SI