시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 29 5 5 35.714%

문제

중국인들은 R 발음을 어려워한다. 중국인 뿐만이 아니더라도 외국어를 말할 때는 많은 사람들이 이런 어려움들을 겪는데, 네덜란드인들은 영어의 th 발음을 S처럼 하고, 스페인 사람들은 V를 B처럼 발음하기도 한다. 

사샤라는 이 세살배기 친구도 비슷한 어려움을 겪고 있다. 좀 더 명확히 말하자면 이 어린이의 부모님의 어려움이겠지만. 아직 나이가 어려서 그런지 몇몇 철자들이 발음이 어려우면 그냥 자기가 발음 하기 쉬운 똑같은 철자들로 바꿔서 발음해버리는 것이다. 그래서 사샤의 부모님은 사샤가 말한걸 듣고 정말로 많은 생각을 해야 겨우 이 친구가 어떤 단어를 말하는지 알아낼 수 있을 정도다.

더 큰 문제는 사샤의 '철자교환기술'이 그리 일정하지 않다는 것을 부모님들이 알아낸 뒤에 일어났다. 맨 앞에 있는 R은 잘 발음하게 된 사샤지만, 단어의 중간에 오는 R은 자기가 발음하기 쉬운 것들로 계속 바꾸고 있는 것이다. 

당신은 사샤의 부모님을 도와 사샤가 도대체 어떤 단어를 말하고 있는지 번역하는 프로그램을 만들어줘야 한다. 사샤가 말한 것에 가장 근접하다고 여겨지는 단어를 사전에 있는 주어진 단어들로부터 하나 뽑아내야하며, 가장 근접한 언어는 사샤가 철자를 최소한으로 바꾼 단어다. 사샤가 어떤 철자의 발음을 어려워하는지 또 어떤 철자로 바꿔버리는지는 주어지지 않는다. 

입력

  • 첫줄에는 테스트 케이스의 개수로 양의 정수 n (0 < n < 10000)이 주어진다
  • 각 테스트 케이스별로:
    • 사샤가 발음한 단어
    • 사전, 주어지는 단어들의 개수 w (0 < w < 10000)
    • w 라인만큼 한 라인당 단어들이 주어진다.

모든 단어들은 소문자로 주어지며 128자를 절대 넘지 않는다. 또한 사전으로 주어지는 단어들은 사샤가 원래 발음한 단어의 길이와 같다. 

출력

각 테스트 케이스별로, 출력값은 한 단어 -사샤가 원래 말한 단어에 가장 가깝다고 여겨지는 단어 - 로 이루어져있다. 만약 여러 단어들이 답으로 가능하다면, 사전에서 가장 먼저나오는 단어를 출력한다. 

예제 입력

1
lolly
5
child
mommy
hello
drink
horse

예제 출력

mommy

힌트