← 返回题目列表

AtCoder · icpc2012autumn_k

J. 上古卷轴

中文机器翻译题面 查看原题

问题陈述

你从魔法师那里购买了3张远古卷轴。这些卷轴都有一根长绳,而且绳的长度都是一样的。他说这些卷轴是进入拥有秘密宝藏的地牢的钥匙串的副本。 不过,他也表示,由于手工复制了很多次,因此字符串会包含一些错误,尽管长度看起来是正确的。

你的工作是从这些字符串中恢复原始字符串。在查找原始字符串时,您决定使用以下假设。

  • 复制的字符串最多包含 d 错误。也就是说,原字符串和复制字符串的汉明距离最多为 d.
  • 如果存在多个候选字符串,则字典顺序最小的字符串是原始字符串。

你能找到原始字符串吗?


输入

输入包含一系列数据集。

每个数据集都具有以下格式:

l d
str_1
str_2
str_3

第一行包含两个整数 l (1 \leq l \leq 100,000)和 d (0 \leq d \leq 5,000.) l 描述了 3 个给定字符串的长度, d 描述了可接受的最大汉明距离。 下面3行给出了字符串,其长度为 l。 这 3 个字符串仅包含小写和大写字母。

输入以包含两个零的行结束,不应对其进行处理。

输出

在一行中打印按字典顺序排列的满足条件的最小值。 如果不存在这样的字符串,则打印 -1.


示例输入

3 1
ACM
IBM
ICM
5 2
iwzwz
iziwi
zwizi
1 0
A
B
C
10 5
jLRNlNyGWx
yyLnlyyGDA
yLRnvyyGDA
0 0

样本输入的输出

ICM
iwiwi
-1
AARAlNyGDA