在基因工程研究中，科学家们经常需要将一个新发现的基因片段与一个庞大的已知基因序列数据库进行比对，以寻找功能或来源上最相似的序列。这种相似度通常通过所谓的“突变距离”来衡量。 突变距离（即莱文斯坦距离）被定义为：将一个基因序列转换为另一个序列所需的最少“点突变”操作次数。允许的点突变操作有三种： 1. 替换 (Substitution)：将一个碱基替换成另一个碱基。 2. 插入 (Insertion)：在一个序列的任意位置插入一个碱基。 3. 删除 (Deletion)：从一个序列中删除任意一个碱基。 你的任务是编写一个程序，对于一个给定的待测基因片段，从数据库中找出所有与之足够相似的基因序列。

输入描述:

第一行是一个整数 ，代表可接受的最大突变容忍度。第二行是一个整数 ，代表基因数据库中序列的总数。接下来 行，每行是一个已知的基因序列。最后一行是待测的基因片段。约束条件：* * * 单个基因序列的长度 满足 。* 为简化模型，所有基因序列只包含小写英文字母。

输出描述:

根据比对结果，分三种情况输出：1. 精确匹配：如果待测基因片段与数据库中的某个序列完全相同，直接输出该序列。2. 模糊匹配：如果不存在精确匹配，则找出所有与待测片段的突变距离小于或等于 的序列。将这些序列首先按突变距离从小到大排序，若距离相同，则按字典序从小到大排序。最后将排序后的结果用空格隔开，在一行内输出。3. 无匹配：如果不存在精确匹配，且数据库中没有任何序列满足突变距离小于或等于 的条件，则输出 None 。

备注:

本题由牛友@Charles 整理上传