In his spare time, Vjeko likes to browse through files in directories. Unfortunately, it seems to him that the console on his computer broke down and now it doesn't correctly print file names that match a certain pattern.
A pattern is a string consisting of lowercase letters of the English alphabet and exactly one asterisk. A file name matches a pattern if the pattern string can be made equal to the file name by replacing the asterisk with an arbitrary string of lowercase letters of the English alphabet (an empty string substitution is also possible). For example, strings abcd
, ad
and anestonestod
all match the pattern a*d
and the string bcd
does not.
Write a program that will, given a pattern and file names, output whether a file name matches the pattern or not.
Input Specification
The first line of input contains the integer , the number of files.
The second line of input contains a string of characters consisting of only lowercase letters of the English alphabet and exactly one asterisk (ASCII value ). The length of the string will not exceed and the asterisk will not be located at the beginning nor at the end of the string.
Each of the following lines contains file names, each in its own line. The file names consist of only lowercase letters of the English alphabet and their length will not exceed .
Output Specification
Output lines. The line should be DA
(Croatian for yes) if the file name matches the pattern or NE
(Croatian for no) if the file name does not match the pattern.
Sample Input 1
3
a*d
abcd
anestonestod
facebook
Sample Output 1
DA
DA
NE
Sample Input 2
6
h*n
huhovdjestvarnomozedocisvastan
honijezakon
atila
je
bio
hun
Sample Output 2
DA
DA
NE
NE
NE
DA
Comments