CF832B.Petya and Exam

It's hard times now. Today Petya needs to score 100 points on Informatics exam. The tasks seem easy to Petya, but he thinks he lacks time to finish them all, so he asks you to help with one..

There is a glob pattern in the statements (a string consisting of lowercase English letters, characters "?" and "*"). It is known that character "*" occurs no more than once in the pattern.

Also, n query strings are given, it is required to determine for each of them if the pattern matches it or not.

Everything seemed easy to Petya, but then he discovered that the special pattern characters differ from their usual meaning.

A pattern matches a string if it is possible to replace each character "?" with one good lowercase English letter, and the character "*" (if there is one) with any, including empty, string of bad lowercase English letters, so that the resulting string is the same as the given string.

The good letters are given to Petya. All the others are bad.

现在是艰难时期。今天，佩佳需要在信息学考试中获得 100 分。这些题目对佩佳来说似乎很简单，但他觉得自己时间不够，无法全部完成，因此他请你帮忙解决其中一道题。

题目中给出一个通配符模式（即由小写英文字母、字符 ? 和 * 组成的字符串）。已知该模式中字符 * 至多出现一次。

此外，还给出 n 个查询字符串，要求对每个查询字符串判断其是否与该模式匹配。

这一切对佩佳来说原本看似简单，但随后他发现，该特殊模式中的通配符含义与通常意义不同。

一个模式能匹配一个字符串，当且仅当可以将每个字符 ? 替换为一个“好”的小写英文字母，且（若存在）将字符 * 替换为任意长度（包括空串）的“坏”的小写英文字母组成的字符串，使得最终得到的字符串与给定字符串完全相同。

“好”的字母已提供给佩佳；其余所有小写英文字母均为“坏”的字母。

The first line contains a string with length from 1 to 26 consisting of distinct lowercase English letters. These letters are good letters, all the others are bad.

The second line contains the pattern — a string s of lowercase English letters, characters "?" and "*" (1 ≤ |s| ≤ 105). It is guaranteed that character "*" occurs in s no more than once.

The third line contains integer n (1 ≤ n ≤ 105) — the number of query strings.

n lines follow, each of them contains single non-empty string consisting of lowercase English letters — a query string.

It is guaranteed that the total length of all query strings is not greater than 105.

第一行包含一个长度为 $1$ 到 $26$ 的字符串，由互不相同的英文小写字母组成。这些字母是“好字母”，其余所有字母均为“坏字母”。

第二行包含一个模式串——一个由英文小写字母、字符 ? 和 *（星号）组成的字符串 $s$（$1 \leq |s| \leq 10^5$）。保证字符 * 在 $s$ 中至多出现一次。

第三行包含一个整数 $n$（$1 \leq n \leq 10^5$）——查询字符串的个数。

接下来 $n$ 行，每行包含一个非空字符串，仅由英文小写字母组成——即一个查询字符串。

保证所有查询字符串的总长度不超过 $10^5$。

Print n lines: in the i-th of them print "YES" if the pattern matches the i-th query string, and "NO" otherwise.

You can choose the case (lower or upper) for each letter arbitrary.

输出 n 行：在第 i 行中，如果模式串与第 i 个查询字符串匹配，则输出 "YES"，否则输出 "NO"。

对于每个字母，你可以任意选择其大小写（小写或大写）。

In the first example we can replace "?" with good letters "a" and "b", so we can see that the answer for the first query is "YES", and the answer for the second query is "NO", because we can't match the third letter.

Explanation of the second example.

• The first query: "NO", because character "*" can be replaced with a string of bad letters only, but the only way to match the query string is to replace it with the string "ba", in which both letters are good.
• The second query: "YES", because characters "?" can be replaced with corresponding good letters, and character "*" can be replaced with empty string, and the strings will coincide.
• The third query: "NO", because characters "?" can't be replaced with bad letters.
• The fourth query: "YES", because characters "?" can be replaced with good letters "a", and character "*" can be replaced with a string of bad letters "x".

在第一个例子中，我们可以将 “?” 替换为合适的字母 “a” 和 “b”，因此第一个查询的答案为 “YES”，而第二个查询的答案为 “NO”，因为我们无法匹配第三个字母。

第二个例子的解释：

• 第一个查询：“NO”，因为字符 “*” 只能被替换为一串坏字母，但匹配查询字符串的唯一方式是将其替换为字符串 “ba”，而其中两个字母均为好字母。
• 第二个查询：“YES”，因为字符 “?” 可以被替换为对应的好字母，且字符 “*” 可以被替换为空字符串，从而使两字符串完全一致。
• 第三个查询：“NO”，因为字符 “?” 不能被替换为坏字母。
• 第四个查询：“YES”，因为字符 “?” 可以被替换为好字母 “a”，且字符 “*” 可以被替换为一串坏字母 “x”。