Glob Só Que Louco
time limit per test
0.25 segundos
memory limit per test
256 megabytes
input
entrada padrão
output
saída padrão

O comando glob, nome curto para global, era um programa presente nas primeiras versões do Unix. Sua função era fazer expansão de uma expressão e passar para outro programa todos os arquivos que casavam com aquele expressão. Como exemplo, a expressão '*' casa com o nome de todos os arquivos, então pode literalmente significar "todos os arquivos". Nos dias atuais, o glob foi englobado por funções de biblioteca, e faz parte da habilidade padrão dos shells.

Porém, Zaphod não trabalha com arquivos no seu dia a dia. Seu trabalho está ligado a criação de um Sistema Gerenciamento de Banco de Dados (SGBD) chamado MyPostcle. Nesse banco de dados, é usado uma linguagem de consulta Só Que Louco (SQL), que permite consultas nesse estilo:

SELECIONE nome, salario DE funcionario ONDE nome EH TIPO 'Zaphod B%' E salario EH TIPO '[1-9]__[34][^9][^8]'

Agora, está na fase do projeto de implementar a funcionalidade do TIPO que é extremamente parecida com os globs do Unix. Ao invés de usar '*' e '?', a sintaxe é um pouco diferente:

O Zadoph fez um algoritmo, mas ele não passou em todos os testes do SGBD. Desesperado, ele agora está recorrendo a você para ajudá-lo, você consegue implementar a funcionalidade de TIPO da linguagem Só Que Louco?

Input

Na primeira linha se encontra um inteiro $$$N$$$ $$$(1 \le N \le 100)$$$, o tamanho do padrão TIPO. Na próxima linha, se encontra o padrão de tamanho $$$N$$$ que é composto de caracteres ASCII de espaço, alfabeto latino maiúsculo e minúsculo, números, '[', ']', '^', '-', '%' e '_'.

É garantido que depois de '[', opcionalmente existe um '^', e sempre existe um conjunto de caracteres não especiais que podem ser caracteres isolados ou intervalos 'A-Z' que tem extremidades pertencentes ao mesmo grupo (maiúsculas com maiúsculas, minúsculas com minúsculas, números com números, espaço com espaço), e finalmente é sempre finalizado por ']'. Os caracteres '[', ']', '-' e '^' não são usados fora deste contexto.

Na linha seguinte, se encontra um inteiro $$$Q$$$ $$$(1 \le Q \le 10^3)$$$, a quantidade de linhas que serão testadas. Nas $$$Q$$$ linhas seguintes, se encontra um inteiro $$$M$$$ $$$(1 \le M \le 100)$$$ que determina o tamanho do texto a ser testado, um espaço, e o texto a ser testado (que não possui espaços no começo ou no final). O texto possui apenas caracteres de espaço, do alfabeto latino maiúsculo e minúsculos e números.

Output

Imprima todos as linhas que casaram com o padrão na ordem que foram dadas na entrada.

Examples

Input
10
Z%aph_d B%
11
17 Zaphod Beeblebrox
20 Ziayphad Bittersweet
21 Ziyaphad Betelgeusian
21 Tricia Marie McMillan
20 Zaphod Beeblebrox II
12 Ford Prefect
23 Zetaphod Beeblebrox III
21 Z123aphad Bittersweet
18 Arthur Philip Dent
20 Zetaphad Bittersweet
21 Z123phad Betelgeusian
Output
Zaphod Beeblebrox
Ziyaphad Betelgeusian
Zaphod Beeblebrox II
Zetaphod Beeblebrox III
Z123aphad Bittersweet
Zetaphad Bittersweet
Input
19
[1-9]__[34][^9][^8]
8
6 100387
6 100487
6 100388
6 900387
7 9003387
6 a03387
6 103487
6 103587
Output
100387
100487
900387
103487