Problem: Problem Statement

You bought 3 ancient scrolls from a magician. These scrolls have a long string, and the lengths of the strings are the same. He said that these scrolls are copies of the key string to enter a dungeon with a secret treasure. However, he also said, they were copied so many times by hand, so the string will contain some errors, though the length seems correct.

Your job is to recover the original string from these strings. When finding the original string, you decided to use the following assumption.

* The copied string will contain at most d errors. In other words, the Hamming distance of the original string and the copied string is at most d.
* If there exist many candidates, the lexicographically minimum string is the original string.



Can you find the orignal string?



Input

The input contains a series of datasets.

Each dataset has the following format:


l d
str_1
str_2
str_3


The first line contains two integers l (1 \leq l \leq 100,000) and d (0 \leq d \leq 5,000.) l describes the length of 3 given strings and d describes acceptable maximal Hamming distance. The following 3 lines have given strings, whose lengths are l. These 3 strings consist of only lower and upper case alphabets.

The input ends with a line containing two zeros, which should not be processed.

Output

Print the lexicographically minimum satisfying the condition in a line. If there do not exist such strings, print `-1`.

Example

Input

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


Output

ICM
iwiwi
-1
AARAlNyGDA

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 100005

enum Type{
	ALL_SAME,
	ALL_DIFFERENT,
	SAME_01,
	SAME_02,
	SAME_12,
};


int LEN,LIMIT;
int count_table[5],rest[3],tmp[3];
char buf[3][SIZE];
Type type[SIZE];


bool isOK(){

	int plus_count = 0;
	int plus_index = -1;

	int num_0 = max(0,count_table[ALL_DIFFERENT]-(rest[0]-count_table[SAME_12]));
	int num_1 = max(0,count_table[ALL_DIFFERENT]-(rest[1]-count_table[SAME_02]));
	int num_2 = max(0,count_table[ALL_DIFFERENT]-(rest[2]-count_table[SAME_01]));

	if(num_0 > 0){
		plus_count++;
		plus_index = 0;
	}
	if(num_1 > 0){
		plus_count++;
		plus_index = 1;
	}
	if(num_2 > 0){
		plus_count++;
		plus_index = 2;
	}

	if(num_0+num_1+num_2 <= count_table[ALL_DIFFERENT])return true;
	if(plus_count >= 2)return false;

	int minus;

	switch(plus_index){
	case 0:

		minus = min(count_table[SAME_12],min(rest[1]-(count_table[ALL_DIFFERENT]+count_table[SAME_02]),
				rest[2]-(count_table[ALL_DIFFERENT]+count_table[SAME_01])));
		break;
	case 1:
		minus = min(count_table[SAME_02],min(rest[0]-(count_table[ALL_DIFFERENT]+count_table[SAME_12]),
						rest[2]-(count_table[ALL_DIFFERENT]+count_table[SAME_01])));
		break;
	case 2:
		minus = min(count_table[SAME_01],min(rest[0]-(count_table[ALL_DIFFERENT]+count_table[SAME_12]),
								rest[1]-(count_table[ALL_DIFFERENT]+count_table[SAME_02])));
		break;
	}

	return num_0+num_1+num_2-minus <= count_table[ALL_DIFFERENT];
}


void func(){

	for(int i = 0; i < 3; i++){

		scanf("%s",buf[i]);
	}

	for(int i = 0; i < 5; i++){

		count_table[i] = 0;
	}

	for(int i = 0; i < 3; i++){

		rest[i] = LIMIT;
	}

	for(int i = 0; i < LEN; i++){

		if(buf[0][i] == buf[1][i] && buf[0][i] == buf[2][i]){

			count_table[ALL_SAME] += 1;
			type[i] = ALL_SAME;

		}else if(buf[0][i] == buf[1][i]){

			count_table[SAME_01] += 1;
			type[i] = SAME_01;

		}else if(buf[0][i] == buf[2][i]){

			count_table[SAME_02] += 1;
			type[i] = SAME_02;

		}else if(buf[1][i] == buf[2][i]){

			count_table[SAME_12] += 1;
			type[i] = SAME_12;

		}else{

			count_table[ALL_DIFFERENT] += 1;
			type[i] = ALL_DIFFERENT;
		}
	}

	if(!isOK()){

		printf("-1\n");
		return;
	}


	vector<char> ANS,work;

	for(int i = 0; i < LEN; i++){

		work.clear();

		work.push_back('A');
		for(int k = 0; k < 3; k++){

			work.push_back(buf[k][i]);
		}
		sort(work.begin(),work.end());
		work.erase(unique(work.begin(),work.end()),work.end());

		count_table[type[i]] -= 1;

		for(int k = 0; k < work.size(); k++){

			for(int p = 0; p < 3; p++){

				tmp[p] = rest[p];
				if(buf[p][i] != work[k]){

					rest[p] -= 1;
				}
			}

			if(isOK()){

				ANS.push_back(work[k]);
				break;
			}

			for(int p = 0; p < 3; p++){

				rest[p] = tmp[p];
			}
		}
	}

	for(int i = 0; i < ANS.size(); i++){

		printf("%c",ANS[i]);
	}
	printf("\n");
}

int main(){

	while(true){

		scanf("%d %d",&LEN,&LIMIT);
		if(LEN == 0 && LIMIT == 0)break;

		func();
	}

	return 0;
}