Pathword Quest

Você recebe uma grade de tamanho n x n composta por letras minúsculas do alfabeto inglês. Sua tarefa é verificar se existe um caminho simples nessa grade que possa ser lido como a string s fornecida.

As letras encontradas ao longo do caminho devem formar a string s na ordem correta.

Entrada

A primeira linha contém um inteiro n (1 ≤ n ≤ 6), que representa o tamanho da grade.

As próximas n linhas contêm n letras minúsculas do alfabeto inglês cada, representando as letras de cada célula da grade.

A última linha contém a string s (1 ≤ |s| ≤ 15), composta por letras minúsculas do alfabeto inglês.

Saída

Imprima YES se existir um caminho simples na grade que forme a string s ao ler as letras em sequência. Caso contrário, imprima NO.

Exemplos

Entrada

Saída

3
a b e
d c f
g h i
abc

YES

3
a b e
d c f
g h i
abce

NO

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue