You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

编辑距离也称莱文斯坦距离，指的是两个字符串之间，由一个转化为另一个所需的最少编辑操作次数，允许的编辑操作包括：

1. 将其中一个字符替换为另一个字符
2. 插入一个字符
3. 删除一个字符

例如，字符串 "ab" 可以通过修改一个字符变为 "ac"，可以通过增加一个字符变为 "acb"，也可以通过删除一个字符变为 "a"，所以 "ab" 与 "ac", "acb", "a" 的编辑距离都为 $1$。当然两个相等的字符串的编辑距离为 $0$。

现在，小 Z 有 $n$ 个英语单词，他用这些单词组成了一个英语词典，这样当他遇到一个单词时，就可以通过查词典的方式来帮助记忆。

具体地，小 Z 将 $n$ 个单词编辑成词典，然后接下来会遇到 $q$ 个需要查询的单词，对于每一个查询单词，如果词典中某一个单词和这个查询的单词的编辑距离 $\le 1$，那么就输出词典中的这个单词。如果不存在这样的单词，就输出 No。

「一些出题人善意的提示」

1. 数据保证答案唯一

2. 字符串 $s$ 与字符串 $t$ 的编辑距离 $\le 1$，有如下 $4$ 情况：

   • $s$ 与 $t$ 相同；$s$ 可以通过删除一个字符变为 $t$；$s$ 可以通过增加一个字符变为 $t$；$s$ 可以通过修改一个字符变为 $t$。

输入格式

第一行输入两个整数 $n,q$ 分别表示词典中单词的个数和询问的单词个数。

接下来 $n$ 行，每行一个一个字符串表示词典中初始的单词。

接下来 $q$ 行，每行一个字符串表示小 Z 这次询问的单词。

输出格式

输出共 $q$ 行，对于每一次询问输出词典中与询问单词编辑距离 $\le 1$ 的单词。如果不存在，则输出 No。

样例 #1

样例输入 #1

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

样例输出 #1

input
input
input
dict
No

提示

对于 $60\%$ 的数据，满足词典中要么只有与询问完全相同的单词，要么答案为 No。

对于 $100\%$ 的数据，满足 $1\le n \le 50,1\le q\le 50$，单词长度 $\le 20$，单词仅由小写字母组成。数据保证每一组询问的答案唯一。