现在日子不好过。今天 Petya 需要在信息学考试中获得 100 分。这些任务对 Petya 来说似乎很简单,但他认为自己没有时间完成所有任务,所以他请你帮忙完成一项任务。
语句中存在 glob 模式(由小写英文字母、字符“?”和“*”组成的字符串)。已知字符“*”在模式中出现不超过一次。
此外,给定n个查询字符串,需要确定每个查询字符串的模式是否匹配。
一切对Petya来说似乎很简单,但随后他发现特殊图案字符与通常的含义不同。
如果可以替换每个字符“?”,则模式与字符串匹配。一个好的小写英文字母,以及字符“*”(如果有的话)与任何一串(包括空的)坏的小写英文字母,使得结果字符串与给定字符串相同。
好信都给了Petya。其他的都不好。
输入
第一行包含一个长度为 1 到 26 的字符串,由不同的小写英文字母组成。这些信都是好信,其他的都是坏信。
第二行包含模式 — 由小写英文字母组成的字符串 s,字符“?”和“*”(1 ≤ |s| ≤ 105)。保证字符“*”在 s 中出现不超过一次。
第三行包含整数 n (1 ≤ n ≤ 105) — 查询字符串的数量。
接下来有 n 行,每行都包含由小写英文字母组成的单个非空字符串 - 查询字符串。
保证所有查询字符串的总长度不大于105。
输出
打印 n 行:如果模式与第 i 个查询字符串匹配,则在第 i 行中打印“YES”,否则打印“NO”。
您可以任意选择每个字母的大小写(小写或大写)。
示例
输入 #1
ab a?a 2 aaa aab
输出 #1
YES NO
输入 #2
abc a?a?a* 4 abacaba abaca apapa aaaaax
输出 #2
NO YES NO YES
注意
在第一个示例中,我们可以替换“?”好的字母“a”和“b”,所以我们可以看到第一个查询的答案是“YES”,第二个查询的答案是“NO”,因为我们无法匹配第三个字母。
第二个示例的说明。
- 第一个查询:“NO”,因为字符“*”只能替换为一串坏字母,但匹配查询字符串的唯一方法是将其替换为字符串“ba”,其中两个字母都是好字母。
- 第二个查询:“YES”,因为字符“?”可以替换为对应的好字母,字符“*”可以替换为空字符串,字符串会重合。
- 第三个查询:“NO”,因为字符“?”不能用坏字母代替。
- 第四个查询:“YES”,因为字符“?”可以用好字母“a”替换,而字符“*”可以用一串坏字母“x”替换。