题目描述

:::align{center} :::

新的审查法已获通过，大量字符和字符串被明确禁止出现在公共出版物中。

具体而言，有 $N$ 个模式被列入黑名单。为简化问题，我们只考虑大写字母，每个模式是一个仅由大写字母构成的字符串。

有关当局对至少含有一个子串与某个被禁模式匹配的字符串实施全面封禁。

若一个子串可以通过选择全部 $26$ 个大写字母的某个排列而变换为某个模式，则称匹配成立。下面给出一些示例。

• $ABB$、$ACC$、$BAA$、$UTT$、$XZZ$ 和 $ZAA$ 两两相互匹配。
• $ABCDECBA$ 与 $TYQAXQYT$ 匹配，但与 $QWEWSEWQ$ 不匹配。

你的目标是设计一个高效的算法，用于判定即将发布的出版物是否合法。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 20$)，表示测试数据的组数。

对于每组测试数据：

• 第一行是被禁模式的数量 $N$ ($1 \le N \le 5000$)。
• 接下来的 $N$ 行，每行包含一个由大写字母组成的模式。
• 第 $N+2$ 行包含一个整数 $M$ ($1 \le M \le 250000$)，表示需要根据上述模式进行判定的字符串数量。
• 接下来的 $M$ 行，每行同样包含一个由大写字母组成的字符串。

对于每组测试数据，所有模式的总长度不超过 $100000$，所有待判定字符串的总长度不超过 $1000000$。

输出格式

对于每组测试数据，输出一行 Case #i: 其后跟随 $M$ 个由空格分隔的字母。对于每个给定的字符串，若被禁止则输出 Y，否则输出 N。

2
2
AAB
ABB
8
TUU
ZZY
UVW
ABABABA
UUVV
TTUUO
EEEE
XY
1
ABCBD
5
UVWXY
UVVVY
UVWVY
YVWVY
VVWVY

Case #1: Y Y N N Y Y N N
Case #2: N N Y N N

提示

翻译由 DeepSeek V4 Pro 完成