치명적인 단어

친구 Sean과 행맨 게임을 하고 있다. Sean이 아주 손쉽게 남의 것을 빼앗는 데 능하다는 이야기는 들었지만, 이 게임은 그만큼 잘하지 못한다. Sean의 불완전한 전략을 이용해 가능한 한 크게 패배하게 만들 수 있는가?

+--+
 |  O
 | /|\       Mystery word: _ a _ a _ a _
 | / \
 |
+-+---+

행맨은 다음과 같이 진행한다.

• 유효한 모든 단어가 들어 있는 사전 D가 있으며, 당신과 Sean 모두 이 사전을 알고 있다. 단어는 a - z 문자로만 이루어진다. 특히 공백은 없다.

• 먼저 D에서 임의의 단어를 선택하고, 각 글자를 빈칸으로 바꿔 칠판에 적는다: _.

• Sean은 자신의 차례에 임의의 글자를 선택하여 그 글자가 단어에 들어 있는지 물을 수 있다. 들어 있다면 그 글자가 있는 모든 위치를 공개한다. 그렇지 않으면 Sean은 점수를 잃는다.

• 단어의 모든 글자가 공개되면 라운드가 끝난다.

• Sean이 점수를 아무리 많이 잃더라도 라운드는 절대 일찍 끝나지 않는다.

Sean은 매우 단순한 전략을 사용한다. 그는 26개의 글자를 어떤 순서로 나열한 목록 L을 만들고, 목록을 한 번에 한 글자씩 차례로 살펴본다. D에 (a) 그가 생각하고 있는 글자를 포함하고, (b) 지금까지 칠판에 적힌 내용 및 Sean이 이전에 추측한 모든 결과와 일치하는 단어가 적어도 하나 있다면 Sean은 그 글자를 추측한다. 그렇지 않으면 그 글자를 건너뛴다. 어느 경우든 Sean은 그다음 목록의 다음 글자로 넘어간다.

Sean의 목록이 주어질 때, Sean이 가능한 한 많은 점수를 잃게 하려면 어떤 단어를 선택해야 하는가? 똑같이 좋은 선택지가 여러 개라면 D에서 가장 먼저 등장하는 단어를 선택해야 한다.

예제

Suppose Sean이 알파벳 순서로 글자를 추측하기로 하고(즉, L = "abcdefghijklmnopqrstuvwxyz"), D에 banana, caravan, pajamas 단어가 들어 있다고 하자. pajamas을 선택하면 게임은 다음과 같이 진행된다.

• 먼저 칠판에 7개의 빈칸 _ _ _ _ _ _ _을 적는다. Sean은 빈칸의 수를 보고 단어가 caravan 또는 pajamas임을 즉시 알게 된다.

• Sean은 a이 L에서 가장 먼저 나오므로 이를 먼저 추측하고, 칠판에 a 글자가 있는 모든 위치를 공개한다: _ a _ a _ a _.

• Sean은 b이 banana에 사용되었음에도 이를 건너뛴다. Sean은 이미 그것이 당신의 단어가 아님을 알고 있다.

• 그런 다음 c이 caravan에 등장하기 때문에 이를 추측한다. 하지만 실제로 선택한 단어에는 등장하지 않으므로 Sean은 점수를 잃고, 추가로 공개되는 것은 없다.

• 소거법에 따라 Sean은 이제 당신의 단어가 pajamas일 수밖에 없음을 알게 되므로, 더는 점수를 잃지 않고 j, m, p, s을 차례로 추측한다.

So Sean은 pajamas을 선택하면 점수를 하나 잃는다. 다른 두 단어 중 어느 것을 선택했더라도 점수를 전혀 잃지 않고 알아냈을 것이다.

제한

1 ≤ T ≤ 10. D의 각 단어는 1개 이상 10개 이하의 문자로 이루어진다. 하나의 테스트 케이스에서 D의 어떤 두 단어도 같지 않다. 메모리 제한: 1GB.

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

1 ≤ N ≤ 100. 1 ≤ M ≤ 10. 시간 제한: 30초.

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

1 ≤ N ≤ 10000. 1 ≤ M ≤ 100. 시간 제한: 60초.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 사전에 있는 단어의 수와 고려할 목록의 수를 나타내는 정수 N과 M이 포함된 한 줄로 시작한다.

다음 N개의 줄에는 사전의 단어가 한 줄에 하나씩 주어진다: $D_{1}$, $D_{2}$, ..., $D_{N}$. 각 단어는 a - z 문자를 임의로 나열한 것이다.

마지막 M개의 줄에는 Sean이 사용할 모든 목록이 한 줄에 하나씩 주어진다: $L_{1}$, $L_{2}$, ..., $L_{M}$. 각 목록의 길이는 정확히 26글자이며, 각 글자를 정확히 한 번씩 포함한다. Sean은 위에서 설명한 대로 이 목록들을 사용해 글자를 추측한다.

각 테스트 케이스마다 "Case #x: $w_{1}$ $w_{2}$ ... $w_{M}$"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), $w_{i}$은 Sean이 $L_{i}$ 순서로 글자를 추측할 때 선택해야 하는 단어이다. 여러 단어가 Sean으로 하여금 같은 수의 점수를 잃게 한다면 사전에서 가장 먼저 등장하는 선택지를 골라야 한다.