Description

作为一名法师，你可以召唤八种元素，这些是“基础”元素。每个基础元素是 $\{Q, W, E, R, A, S, D, F\}$ 中的一个字符。当你召唤一个元素时，它会被添加到你的元素列表的末尾。例如：如果你先召唤 $W$，再召唤 $A$（我们简称为“召唤 $WA$”），那么你的元素列表将变为 $[W, A]$。

我们会指定一些基础元素对，这些元素对可以组合成非基础元素（其余 18 个大写字母）。例如，$Q$ 和 $F$ 可以组合成 $T$。如果某一时刻，这对元素出现在元素列表的末尾，那么这两个元素会被立即移除，并用它们组合成的新元素替换。例如，如果元素列表为 $[A, Q, F]$ 或 $[A, F, Q]$，那么它会变为 $[A, T]$。

我们还会指定一些基础元素对，它们彼此“对立”。当你召唤一个元素后，如果它没有立即与其他元素组合成新元素，并且它与元素列表中的某个元素是对立的，那么你的整个元素列表会被清空。

例如，假设 $Q$ 和 $F$ 组合成 $T$，$R$ 和 $F$ 是对立的。那么依次召唤以下元素（从左到右）会有如下结果：

• $QF \rightarrow [T]$（$Q$ 和 $F$ 组合成 $T$）
• $QEF \rightarrow [Q, E, F]$（$Q$ 和 $F$ 没有同时出现在末尾，无法组合）
• $RFE \rightarrow [E]$（$F$ 和 $R$ 对立，列表被清空，然后召唤 $E$）
• $REF \rightarrow []$（$F$ 和 $R$ 对立，列表被清空）
• $RQF \rightarrow [R, T]$（$QF$ 组合成 $T$，列表不会被清空）
• $RFQ \rightarrow [Q]$（$F$ 和 $R$ 对立，列表被清空）

给定一系列要召唤的元素，最终你的元素列表中会有哪些元素？

Input Format

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据由一行组成，内容如下，元素之间用空格分隔：

首先是一个整数 $C$，接着是 $C$ 个字符串，每个字符串有三个字符：前两个是基础元素，第三个是它们组合成的非基础元素。接下来是一个整数 $D$，然后是 $D$ 个字符串，每个字符串有两个字符，表示这两个基础元素是对立的。最后是一个整数 $N$，接着是一个长度为 $N$ 的字符串，表示你要依次召唤的基础元素（从左到右依次召唤）。

Output Format

对于每个测试用例，输出一行，格式为“Case #$x$: $y$”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是最终元素列表，格式为“$[e_0, e_1, \dots]$”，其中 $e_i$ 是最终元素列表中的第 $i$ 个元素。具体格式请参考样例输出。

5
0 0 2 EA
1 QRI 0 4 RRQR
1 QFT 1 QF 7 FAQFDFQ
1 EEZ 1 QE 7 QEEEERA
0 1 QW 2 QW

Case #1: [E, A]
Case #2: [R, I, R]
Case #3: [F, D, T]
Case #4: [Z, E, R, A]
Case #5: []

Hint

数据范围

• $1 \leq T \leq 100$。
• 每对基础元素最多只会出现在一个组合中，但它们既可以组合也可以对立。
• 没有基础元素会与自身对立。
• 与游戏 Magicka 不同，元素列表长度没有限制。

小数据集（10 分，测试点 1 - 可见）

• $0 \leq C \leq 1$。
• $0 \leq D \leq 1$。
• $1 \leq N \leq 10$。
• 时间限制：3 秒。

大数据集（15 分，测试点 2 - 隐藏）

• $0 \leq C \leq 36$。
• $0 \leq D \leq 28$。
• $1 \leq N \leq 100$。
• 时间限制：6 秒。

由 ChatGPT 4.1 翻译