#4405. 词典 (dict)

词典 (dict)

[丛雨]英语水平不是很好,所以她请你写一个词典来解决这个问题。这样当她有疑问的时候就可以用这个词典了。 具体来说,丛雨首先会给你 nn 个单词,这些单词组成了词典。接着 qq 次询问,每次询问给你一个单词,你需要告诉丛雨词典中与这个单词编辑距离不超过 11 的单词是什么。如果不存在这样的单词,请输出No,保证答案唯一。 如果你不知道编辑距离的定义,你只需要知道若字符串 ss 与字符串 tt 的编辑距离不超过 11 说明,sstt 相等,或者 sstt 在删去一个字符的结果,或者 sstt 在一个位置加上一个字符的结果,或者 ss 是将 tt 中的一个字符修改为另一个的结果。

输入格式(dict.in)

第一行两个整数 nn , qq 。 接下来 nn 行,每行一个字符串表示词典中初始的单词。 接下来 qq 行,每行一个字符串表示丛雨这次询问的单词。

输出格式(dict.out)

qq 行,每行一个词典中的单词,并且这个单词是词典中与询问单词编辑距离不超过 11 的单词。如果不存在这样的单词,则输出No

输入样例

5 5
input
output
example
cjiajia
dict
nput
inpuxt
input
dicti
ditc

输出样例

input
input
input
dict
No

数据范围

对于 60%60\% 的数据,满足词典中要么只有与询问完全相同的单词,要么答案为No。 对于 100%100\% 的数据,满足 n50,q50,单词长度20n \le 50,q \le 50, 单词长度 \le 20 ,单词仅由小写字母组成。