问题陈述

你从一位魔术师那里购买了三卷古代卷轴。这些卷轴上有一长串字符，而且字符串的长度都相同。他说这些卷轴是进入一个藏有秘宝的地牢的关键字符串的副本。然而，他还说，这些字符串是通过手工复制了很多次，所以字符串中可能包含一些错误，尽管长度看起来是正确的。

你的任务是从这些字符串中恢复出原始字符串。在寻找原始字符串时，你决定使用以下假设。

• 复制的字符串最多包含 $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

资源名称

JAG Practice Contest for ACM-ICPC Asia Regional 2012