Magicka Element Combining

You are a wizard, and you can invoke eight base elements. Each base element is one of the characters Q, W, E, R, A, S, D, F. Invoking an element appends it to your element list. For example, invoking W and then A (call that invoking WA for short) leaves the element list [W, A].

The input gives pairs of base elements that combine into a non-base element. The non-base elements are the other 18 capital letters. Say Q and F combine into T. The moment the last two entries of the element list form such a pair, both are removed and replaced by the element they form. Under that rule, an element list that becomes [A, Q, F] or [A, F, Q] turns into [A, T] right away.

The input also gives pairs of base elements that are opposed to each other. Right after you invoke an element, if it was not consumed by a combination and the element list holds an element opposed to it, the whole element list is cleared.

Suppose Q and F combine into T, and R and F are opposed. Invoking the characters below from left to right gives these results.

• QF → [T]. Q and F combine into T.
• QEF → [Q, E, F]. Q and F never sit at the end of the list together, so they cannot combine.
• RFE → [E]. F and R are opposed, so the list is cleared, and then E is invoked.
• REF → []. F and R are opposed, so the list is cleared.
• RQF → [R, T]. Q and F combine into T, so the list is not cleared.
• RFQ → [Q]. F and R are opposed, so the list is cleared.

Given the elements to invoke, report what the element list holds once all of them are invoked.

The first line has the number of test cases $T$. Each of the next $T$ lines holds one test case as space-separated values in this order.

First an integer $C$, then $C$ strings of three characters each: two base elements followed by a non-base element, meaning that the two base elements combine into that non-base element. Next an integer $D$, then $D$ strings of two characters each: two base elements that are opposed to each other. Last an integer $N$, then one string of $N$ characters, the base elements you invoke, leftmost character first, one at a time.

Limits

• $1 \le T \le 100$
• $0 \le C \le 36$
• $0 \le D \le 28$
• $1 \le N \le 100$
• A pair of base elements appears in at most one combination. The same pair may appear in a combination and also be opposed.
• No base element is opposed to itself.
• Unlike in the computer game Magicka, the element list has no length limit.

For each test case print one line in the format Case #x: y, where x is the test case number starting from 1 and y is the final element list written as [e0, e1, ...]. Here ei is the i-th element of the list, and elements are separated by one comma and one space. An empty list prints as [].