题目内容

在使用命令行工具时，经常会出现手工输入错字母的情况，如想要输入：

git clone

输入成了

git clane

因此为了命令行工具更易用，需要从支持的子命令列表中找到最相似的子命令提示给用户。最相似的定义为最短莱文斯坦距离，即两个字符串之间，由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括：

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

输入描述

第一行给出可提示的最短距离 D，第二行给出子命令数量 N，后面 N 行给出所有的子命令列表，最后一行给出用户输入的子命令。

• 1 <= D <= 5
• 1 <= N <= 30000
• 单个子命令长度 2 <= L <= 25，子命令只包含小写字母

输出描述

输出为分三种情况：

1. 用户输入的子命令正确匹配上某个子命令参数，输出原命令。
2. 用户输入的子命令没有匹配上某个子命令参数，但是符合提示要求，则输出提示命令。如 clone 如果符合提示要求的子命令有多个，则按距离从小到大排序后输出，同一个距离内还有多个的按字母序从小到大输出。
3. 用户输入的子命令没有匹配上某个子命令参数，且没有符合提示要求的子命令，则输出 None

样例1

输入

2
3
clone
checkout
switch
clone

输出

clone

说明

第一行值为2，表示当前输入不能完全正确匹配某个子命令时，则将其最短距离小于2的子命令作为提示输出。第二行为3，表示命令行实际有3个子命令，分别为后续3行。最后一行为用户实际的输入。由于用户没有命中具体的子命令，而 clone 与用户输入的距离为1，满足小于2的要求，因此输出 clone。

样例2

输入

2
3
clone
checkout
switch
create

输出

None

说明

输入的三个子命令中没有满足与 create 距离小于等于2的，因此输出 None。

样例3

输入

2
5
aprint
bprint
aprint
bbprint
output
print

输出

aprint bprint aprint bbprint

说明

子命令中有四个满足与 print 的距离小于等于2，其中 aprint 与 bprint 与目标的距离为1，先将其排序并输出，aprint bbprint 与目标的距离为2，排序后接在前面输出后继续输出。