Submeta sua solução

Nome do arquivo: senha.x, onde x deve ser c, cpp, java, js ou py

Senha da Vó Zinha

Vó Zinha foi sempre muito cuidadosa com as senhas que usa para suas atividades na Internet, como compras, redes sociais e correio eletrônico, e é especialmente cuidadosa com a senha do banco.

No entanto, como está ficando um pouco esquecida das coisas, ela resolveu deixar sua senha do banco escrita, para o caso de necessidade. Obviamente, ela não escreveu simplesmente a senha num papel! Ela inventou uma forma de proteger a senha, mesmo estando escrita, e contou somente para você como fazer para recuperar a senha.

Com um pedaço de papel que Vó Zinha guardou na gaveta onde guarda também suas meias ela fez o seguinte:

Vó Zinha então contou para você como recuperar a senha:

Por exemplo, considere que no papel esteja escrito (• representa uma letra borrada):

x•yy•z
ab
cd
3
Fazendo as substituições, a lista das possíveis senhas é xayycz, xbyycz, xayydz, xbyydz .

Ordenando as possíveis senha obtemos xayycz, xayydz, xbyycz, xbyydz, e portanto a senha correta é xbyycz (a terceira da lista ordenada).

Hoje Vó Zinha precisa pagar uma conta pela internet e não se recorda da senha do banco. Ela pediu que você pegue o pedaço de papel guardado na gaveta e a ajude a recuperar a senha.

Entrada

A primeira linha da entrada contém três números inteiros N, M e K, respectivamente o número de caracteres da senha, o número de letras borradas da senha e o comprimento de cada palavra. A segunda linha contem uma cadeia de caracteres de comprimento N, a senha escrita no papel, com o caractere `#' (cerquilho) representando as letras borradas. Cada uma das M linhas seguintes contém uma palavra Si, sendo que a Si-ésima palavra contém as letras para substituir a i-ésima letra borrada da senha. A última linha contém um número inteiro P, o número de ordem da senha correta na lista ordenada de possíveis senhas.

Saída

Seu programa deve produzir uma única linha, contendo uma única cadeia de caracteres, a senha correta.

Restrições

Informações sobre a pontuação

Exemplos

Entrada
6 2 2
x#yy#z
ab
cd
3
Saída
xbyycz
	

 

Entrada
4 1 3
abc
2
Saída
bgof
	

 

Volta ao início