← 返回题目列表

Codeforces · 2000/C

C. 数字字符串模板

中文机器翻译题面 查看原题

Kristina 有一个数组 $$$a$$$,称为模板,由 $$$n$$$ 整数组成。她还有 $$$m$$$ 字符串,每个字符串仅由小写拉丁字母组成。字符串编号从 $$$1$$$ 到 $$$m$$$。她想检查哪些字符串与模板匹配。

如果同时满足以下所有条件,则字符串 $$$s$$$ 被视为与模板匹配:

- 字符串 $$$s$$$ 的长度等于数组 $$$a$$$ 中的元素数量。
- $$$a$$$ 中的相同数字对应于 $$$s$$$ 中的相同符号。因此,如果 $$$a_i = a_j$$$,则 $$$s_i = s_j$$$ 对于 ($$$1 \le i, j \le n$$$)。
- $$$s$$$ 中的相同符号对应于 $$$a$$$ 中的相同数字。因此,如果 $$$s_i = s_j$$$,则 $$$a_i = a_j$$$ 对于 ($$$1 \le i, j \le n$$$)。

例如,如果 $$$a$$$ = [$$$3, 5, 2, 1, 3$$$],则字符串“abfda”与模板匹配,而字符串“afbfa”则不匹配,因为字符“f”对应于数字 $$$1$$$ 和 $$$5$$$。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

以下描述针对测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 中的元素数量。

每个测试用例的第二行恰好包含 $$$n$$$ 整数 $$$a_i$$$ ($$$-10^9 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

每个测试用例的第三行包含一个整数 $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — 要检查模板匹配的字符串数量。

以下是 $$$m$$$ 字符串,每个字符串包含一个非空字符串 $$$s_j$$$ ($$$1 \le |s_j| \le 2 \cdot 10^5$$$),由小写拉丁字母组成。

保证所有测试用例的$$$n$$$总和不超过$$$2 \cdot 10^5$$$,并且所有字符串的长度总和不超过$$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$m$$$ 行。在第 $$$i$$$ 行 ($$$1 \le i \le m$$$) 输出:

- “YES”,如果索引为 $$$i$$$ 的字符串与模板匹配;
- 否则为“否”。

您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

3
5
3 5 2 1 3
2
abfda
afbfa
2
1 2
3
ab
abc
aa
4
5 -3 5 -3
4
aaaa
bcbc
aba
cbcb

输出 #1

YES
NO
YES
NO
NO
NO
YES
NO
YES

注意

第一个测试用例在问题陈述中进行了解释。