简介

Magicka™ 是由 Arrowhead Game Studios 开发的一款动作冒险游戏。在 Magicka 中，你扮演一名巫师，通过调用并组合元素来创造魔法。本题的灵感来源于此，但并不要求你玩过 Magicka。

注意：“调用”（invoke）在此处是一个技术术语，你无需了解其常规英语含义。

题目描述

作为一名巫师，你可以调用八种“基础”元素。每个基础元素都是 {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 → [T] （Q 和 F 组合成 T）
• QEF → [Q, E, F] （Q 和 F 无法组合，因为它们在列表末尾时中间隔了 E）
• RFE → [E] （F 和 R 对立，列表被清空；然后调用 E）
• REF → [] （F 和 R 对立，列表被清空）
• RQF → [R, T] （QF 组合成 T，因此列表未被清空）
• RFQ → [Q] （F 和 R 对立，列表被清空）

给定一系列要调用的元素，请问最终的元素列表是什么？

输入格式

输入的第一行包含测试用例的数量 T。接下来是 T 个测试用例。每个测试用例由一行组成，包含以下以空格分隔的元素：

首先是一个整数 C，后跟 C 个字符串，每个字符串包含三个字符：两个基础元素后跟一个非基础元素。这表示这两个基础元素组合成该非基础元素。接下来是一个整数 D，后跟 D 个字符串，每个字符串包含两个字符：一对互相对立的基础元素。最后是一个整数 N，后跟一个包含 N 个字符的字符串：你要调用的基础元素序列。你将按照字符串中出现的顺序（从左到右），一次一个地调用它们。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 x 是用例编号（从 1 开始），y 是格式为 "[e₀, e₁, ...]" 的列表，其中 e_i 是最终元素列表中的第 i 个元素。请参考样例输出。

数据范围

$1 \le \mathbf{T} \le 100$。

每对基础元素最多只能出现在一个组合中，尽管它们可能既出现在组合中又互相对立。

没有任何基础元素与自身对立。

与电脑游戏 Magicka 不同，元素列表的长度没有限制。

内存限制：1GB。

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

$0 \le \mathbf{C} \le 1$。

$0 \le \mathbf{D} \le 1$。

$1 \le \mathbf{N} \le 10$。

时间限制：2 秒。

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

$0 \le \mathbf{C} \le 36$。

$0 \le \mathbf{D} \le 28$。

$1 \le \mathbf{N} \le 100$。

时间限制：4 秒。

样例

样例输入 1

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

样例输出 1

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

Magicka™ 是 Paradox Interactive AB 的商标。Paradox Interactive AB 不认可且未参与 Google Code Jam。