Magicka

마법사인 당신은 "기본" 원소인 여덟 가지 원소를 불러낼 수 있다. 각 기본 원소는 {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가 원소 목록의 끝에 함께 있었던 적이 없으므로 결합할 수 없다)

• RFE → [E] (F와 R이 서로 대립하므로 목록이 비워지고, 그다음 E를 불러낸다)

• REF → [] (F와 R이 서로 대립하므로 목록이 비워진다)

• RQF → [R, T] (QF가 결합하여 T를 만들므로 목록은 비워지지 않는다)

• RFQ → [Q] (F와 R이 서로 대립하므로 목록이 비워진다)

불러낼 원소 목록이 주어질 때, 모두 불러낸 뒤 원소 목록에는 무엇이 남는가?

제한

1 ≤ T ≤ 100. 각 기본 원소 쌍은 하나의 결합에만 함께 등장할 수 있지만, 한 결합에 등장하면서 동시에 서로 대립할 수도 있다. 어떤 기본 원소도 자기 자신과 대립하지 않는다. 컴퓨터 게임 Magicka와 달리 원소 목록의 길이에는 제한이 없다. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

0 ≤ C ≤ 1. 0 ≤ D ≤ 1. 1 ≤ N ≤ 10. 시간 제한: 30초.

큰 데이터 세트 (테스트 세트 2 - 비공개)

0 ≤ C ≤ 36. 0 ≤ D ≤ 28. 1 ≤ N ≤ 100. 시간 제한: 60초.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 이루어지며, 다음 항목들이 공백으로 구분되어 순서대로 주어진다.

먼저 정수 C가 주어지고, 이어서 각각 문자 세 개를 포함하는 C개의 문자열이 주어진다. 각 문자열은 두 기본 원소와 그 뒤에 오는 기본 원소가 아닌 원소로 이루어진다. 이는 두 기본 원소가 결합하여 기본 원소가 아닌 원소를 만든다는 뜻이다. 다음으로 정수 D가 주어지고, 이어서 각각 문자 두 개를 포함하는 D개의 문자열이 주어진다. 각 문자열은 서로 대립하는 두 기본 원소로 이루어진다. 마지막으로 정수 N이 주어지고, 이어서 불러내야 할 기본 원소의 나열인 N개의 문자를 포함하는 문자열 하나가 주어진다. 문자열에 나타나는 순서대로(가장 왼쪽 문자부터 그다음 문자로) 한 번에 하나씩 불러낸다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 케이스 번호이며(1부터 시작), y는 "$[e_{0}, e_{1}, ...]$" 형식의 목록이고, $e_{i}$는 최종 원소 목록의 $i^{th}$번째 원소이다. 예시는 예제 출력을 참고한다.

Magicka™는 Paradox Interactive AB의 상표이다. Paradox Interactive AB는 Google Code Jam을 보증하지 않으며 이에 관여하지 않는다.