P3025 [USACO11OPEN] Forgotten Password S

题目描述

给出一串长度为 $L$ 的字符串（密码） 和 $n$ 个单词的词典。密码中部分字母为 ? ，表示该位置的字母不记得了。密码由若干个词典中单词组成。要求还原密码的所有字母，如有多个答案给出最小字典序的结果。

输入格式

第一行两个整数 $L \ n(1 \le L,n \le 1000)$。

下来一行一串字符串，表示需要还原的密码。

下来 $n$ 行，每行一个单词（单词长度小于等于20）。

输出格式

一行一个字符串，表示还原的最小字典序密码。

输入输出样例 #1

输入 #1

15 6 
a??l?ban??????? 
apple 
cow 
farmer 
banana 
bananas 
pies

输出 #1

applebananapies