매지카 원소 조합

당신은 마법사이고 기본 원소 여덟 개를 소환할 수 있다. 기본 원소는 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]. Q와 F가 결합해 T가 되므로 목록을 비우지 않는다.
• RFQ → [Q]. F와 R이 상극이라 목록을 비운다.

소환할 원소의 순서가 주어질 때, 전부 소환한 뒤 원소 목록에 무엇이 남는지 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에 테스트 케이스가 하나씩 주어지며, 각 줄에는 공백으로 구분된 값이 다음 순서로 들어 있다.

먼저 정수 $C$가 오고, 그 뒤에 세 글자짜리 문자열 $C$개가 온다. 각 문자열은 기본 원소 두 개와 기본이 아닌 원소 하나로 이루어지며, 앞의 두 기본 원소가 결합해 뒤의 원소를 만든다는 뜻이다. 다음으로 정수 $D$가 오고, 그 뒤에 두 글자짜리 문자열 $D$개가 온다. 각 문자열은 서로 상극인 기본 원소 두 개다. 마지막으로 정수 $N$이 오고, 그 뒤에 길이가 $N$인 문자열 하나가 온다. 이 문자열은 소환할 기본 원소의 순서이며, 왼쪽 글자부터 하나씩 차례로 소환한다.

제한

• $1 \le T \le 100$
• $0 \le C \le 36$
• $0 \le D \le 28$
• $1 \le N \le 100$
• 기본 원소 쌍 하나는 많아야 한 가지 결합에만 나타난다. 같은 쌍이 결합에도 나타나면서 서로 상극일 수는 있다.
• 자기 자신과 상극인 기본 원소는 없다.
• 컴퓨터 게임 매지카와 달리 원소 목록의 길이에는 제한이 없다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 최종 원소 목록을 [e0, e1, ...] 형식으로 쓴 것이다. ei는 목록의 i번째 원소이며, 원소 사이는 쉼표 하나와 공백 하나로 구분한다. 목록이 비어 있으면 []를 출력한다.