Background

In his spare time, Vjeko likes browsing files in a directory.

Problem Description

A pattern string is a string consisting of lowercase English letters and one asterisk.

The asterisk can be replaced by a string consisting of lowercase letters. If, after replacement, the pattern string becomes equal to a filename, then the filename matches the pattern.

For example, the strings abcd, ad, and anestonestod all match the pattern a*d, while the string bcd does not match.

Write a program that is given a pattern and some filenames, and outputs whether each filename matches the pattern.

Input Format

The first line contains an integer $N$, the number of files.

The second line contains a string consisting only of lowercase English letters and one asterisk.

The length of the string will not exceed $100$, and the asterisk will not be at the beginning or the end of the string.

Each of the next $N$ lines contains a filename.

Each filename consists only of lowercase English letters, and its length does not exceed $100$.

Output Format

Output a total of $N$ lines.

For each filename, output DA if it matches; otherwise output NE.

3
a*d
abcd
anestonestod
facebook

DA
DA
NE

6
h*n
huhovdjestvarnomozedocisvastan
honijezakon
atila
je
bio
hun 

DA
DA
NE
NE
NE
DA

Hint

Constraints

$1\le N\le 100$.

Notes

This problem is translated from COCI2013-2014 CONTEST #6 T1 VJEKO.

Translated by ChatGPT 5