문제
은성이는 자신이 주로 이용하던 jungol 사이트의 암호를 잃어버렸다. 다행히도 암호에 대한 약간의 정보를 알고 있었다. 은성이는 자신의 암호가 길이가 L인 알파벳 소문자로 이뤄져 있으며, 회원에 가입할 때 자신이 가지고 있는 사전에서 여러 단어를 조합하여 암호를 만들었음을 기억하고 있었다. 그리고 암호의 일부 위치에 해당하는 문자가 무엇인지도 알고 있다.
은성이가 생각하고 있는 암호가 "a??l?ban???????" 라고 하자. 여기서 ?는 현재 해당 위치의 문자를 모르는 것이다. 그리고 사전에는 다음과 같은 단어들이 주어져있다.
• apple • cow • farmer • banana • bananas • pies
이때 암호로는 "applebananapies" 혹은 "applebananascow"등이 가능하다. 은성이가 알고 있는 정보가 주어질 때 가능한 암호를 찾아 출력하는 프로그램을 작성하라. 만약 위와 같이 가능한 조합이 여럿 나올 경우, 사전순으로 가장 먼저 나오는 암호를 출력한다.
입력
입력의 첫 줄에는 암호의 길이를 뜻하는 L ( 1 ≤ L ≤ 1,000 )과 사전에 포함된 단어의 개수 NW ( 1 ≤ NW ≤ 1,000 )가 입력된다.
두번째 줄에는 현재 은성이가 부분적으로 알고 있는 길이가 L인 암호가 입력된다.
다음 줄 부터 NW개의 단어가 한줄에 하나씩 입력되며, 이는 사전에 포함된 단어들을 뜻한다. 단어는 길이 20자 이하의 영문 소문자로 이뤄져 있으며, 같은 단어가 여러번 들어오는 경우는 존재하지 않는다.
출력
입력에 대해 복원된 암호를 출력한다. 만약 여러경우가 가능할 경우 사전순으로 가장 앞선 경우를 출력한다.
예제
15 6
a??l?ban???????
apple
cow
farmer
banana
bananas
pies
applebananapies
로그인해야 코드를 작성할 수 있어요.