치명적인 단어 (스몰)

문제

행맨 게임을 친구 션과 한다. 션은 이 게임을 잘 하지 못한다. 션의 허술한 전략을 이용해서 점수를 최대한 많이 잃게 만들어 보자.

 +--+
 |    O
 |   / | \       가려진 단어: _ a _ a _ a _
 |    /  \
 |
+-+---+

행맨의 규칙은 다음과 같다.

유효한 단어를 모은 사전 D가 있고, 나와 션 모두 그 내용을 안다. 단어는 a부터 z까지의 문자로만 이루어지며 공백은 없다.
나는 D에서 단어 하나를 골라 칠판에 적되, 모든 글자를 밑줄 _로 가린다.
션은 자기 차례에 글자 하나를 골라 그 글자가 단어에 들어 있는지 묻는다. 들어 있으면 나는 그 글자가 나오는 위치를 모두 공개한다. 들어 있지 않으면 션이 1점을 잃는다.
단어의 모든 글자가 공개되면 라운드가 끝난다.
션이 점수를 아무리 많이 잃어도 라운드가 중간에 끝나지는 않는다.

션의 전략은 아주 단순하다. 26개의 글자를 어떤 순서로 나열한 목록 L을 만들고 앞에서부터 한 글자씩 살펴본다. 지금 보고 있는 글자에 대해 (a) 그 글자를 포함하면서 (b) 칠판에 적힌 내용과 션의 이전 추측 결과에 모두 들어맞는 단어가 D에 하나라도 있으면 션은 그 글자를 추측한다. 없으면 건너뛴다. 어느 쪽이든 션은 목록의 다음 글자로 넘어간다.

션의 목록이 주어질 때, 션이 점수를 가장 많이 잃게 하려면 어떤 단어를 골라야 하는가? 잃는 점수가 같은 단어가 여럿이면 D에서 먼저 나오는 단어를 고른다.

규칙이 적용되는 방식

션이 알파벳 순서로 추측하고(즉 L = abcdefghijklmnopqrstuvwxyz), D에 banana, caravan, pajamas가 들어 있다고 하자. 내가 pajamas를 고르면 라운드는 이렇게 흘러간다.

칠판에 밑줄 7개 _ _ _ _ _ _ _를 적는다. 밑줄 개수만 보고도 션은 단어가 caravan 아니면 pajamas임을 안다.
션은 L의 첫 글자인 a를 추측하고, 나는 a가 나오는 위치를 모두 공개한다: _ a _ a _ a _.
banana에 b가 쓰이지만 션은 b를 건너뛴다. banana가 답이 아니라는 것을 이미 알기 때문이다.
다음으로 c를 추측한다. caravan에 c가 있기 때문이다. 내가 고른 단어에는 c가 없으므로 션은 1점을 잃고, 새로 공개되는 글자도 없다.
남은 후보가 pajamas뿐이므로 션은 j, m, p, s를 차례로 추측하고 점수를 더 잃지 않는다.

이렇게 pajamas를 고르면 션은 1점을 잃는다. 나머지 두 단어 중 어느 쪽을 골랐다면 션은 한 점도 잃지 않았을 것이다.

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 사전에 있는 단어의 수 N과 살펴볼 목록의 수 M이 주어진다.

다음 N개 줄에는 사전의 단어 $D_1, D_2, \dots, D_N$ 이 한 줄에 하나씩 주어진다. 각 단어는 a부터 z까지의 문자로 이루어진 임의의 문자열이다.

마지막 M개 줄에는 션이 사용할 목록 $L_1, L_2, \dots, L_M$ 이 한 줄에 하나씩 주어진다. 각 목록은 정확히 26글자이며 알파벳 소문자가 각각 정확히 한 번씩 나온다. 션은 이 목록을 위에서 설명한 방식으로 사용해 글자를 추측한다.

제한

$1 \le T \le 10$
$1 \le N \le 100$
$1 \le M \le 10$
D에 있는 각 단어의 길이는 1 이상 10 이하이다.
한 테스트 케이스 안에서 같은 단어가 두 번 나오지 않는다.

출력

각 테스트 케이스마다 Case #x: w1 w2 ... wM 형식으로 한 줄씩 출력한다. x는 테스트 케이스 번호(1부터 시작)이고, $w_i$ 는 션이 $L_i$ 의 순서로 글자를 추측할 때 내가 골라야 하는 단어다. 션이 잃는 점수가 같은 단어가 여럿이면 사전에서 먼저 나오는 단어를 출력한다.