Problem: Marina loves strings of the same length and Vasya loves when there is a third string, different from them in exactly t characters. Help Vasya find at least one such string.

More formally, you are given two strings s1, s2 of length n and number t. Let's denote as f(a, b) the number of characters in which strings a and b are different. Then your task will be to find any string s3 of length n, such that f(s1, s3) = f(s2, s3) = t. If there is no such string, print  - 1.

Input

The first line contains two integers n and t (1 ≤ n ≤ 105, 0 ≤ t ≤ n).

The second line contains string s1 of length n, consisting of lowercase English letters.

The third line contain string s2 of length n, consisting of lowercase English letters.

Output

Print a string of length n, differing from string s1 and from s2 in exactly t characters. Your string should consist only from lowercase English letters. If such string doesn't exist, print -1.

Examples

Input

3 2
abc
xyc


Output

ayd

Input

1 0
c
b


Output

-1

Solution (in JAVA):

Solution:
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;
import java.util.Scanner;

public class Main {

    private final int MOD = (int) 1e9 + 7;

    public void solve() {
	Scanner scanner = new Scanner(System.in);
	int n = scanner.nextInt();
	int t = scanner.nextInt();
	String string1 = scanner.next();
	String string2 = scanner.next();
	int sameCnt = 0;
	for (int i = 0; i < n; i++) {
	    if (string1.charAt(i) == string2.charAt(i)) {
		sameCnt++;
	    }
	}

	int mustSame = n - t;
	int diffCnt = n - sameCnt;
	int halfDiff = diffCnt / 2;
	if (halfDiff + sameCnt < mustSame) {
	    System.out.println(-1);
	    return;
	}

	int diffSame = mustSame - sameCnt;
	StringBuilder builder = new StringBuilder();
	if (diffSame <= 0) {
	    // same内で調整可能
	    for (int i = 0; i < n; i++) {
		char c1 = string1.charAt(i);
		char c2 = string2.charAt(i);
		if (c1 != c2 || mustSame <= 0) {
		    for (int j = 0; j < 26; j++) {
			char c = (char) (j + 'a');
			if (c != c1 && c != c2) {
			    builder.append(c);
			    break;
			}
		    }
		} else {
		    builder.append(c1);
		    mustSame--;
		}

	    }
	    System.out.println(builder.toString());
	} else {
	    int diffSame1 = 0;
	    int diffSame2 = 0;
	    for (int i = 0; i < n; i++) {
		char c1 = string1.charAt(i);
		char c2 = string2.charAt(i);
		if (c1 == c2) {
		    builder.append(c1);
		    continue;
		}

		if (diffSame1 < diffSame) {
		    builder.append(c1);
		    diffSame1++;
		} else if (diffSame2 < diffSame) {
		    builder.append(c2);
		    diffSame2++;
		} else {
		    for (int j = 0; j < 26; j++) {
			char c = (char) (j + 'a');
			if (c != c1 && c != c2) {
			    builder.append(c);
			    break;
			}
		    }
		}
	    }
	    System.out.println(builder.toString());
	}

    }

    public static void main(String[] args) {
	new Main().solve();
    }
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
	if (ptr < buflen) {
	    return true;
	} else {
	    ptr = 0;
	    try {
		buflen = in.read(buffer);
	    } catch (IOException e) {
		e.printStackTrace();
	    }
	    if (buflen <= 0) {
		return false;
	    }
	}
	return true;
    }

    private int readByte() {
	if (hasNextByte())
	    return buffer[ptr++];
	else
	    return -1;
    }

    private static boolean isPrintableChar(int c) {
	return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
	while (hasNextByte() && !isPrintableChar(buffer[ptr]))
	    ptr++;
    }

    public boolean hasNext() {
	skipUnprintable();
	return hasNextByte();
    }

    public String next() {
	if (!hasNext())
	    throw new NoSuchElementException();
	StringBuilder sb = new StringBuilder();
	int b = readByte();
	while (isPrintableChar(b)) {
	    sb.appendCodePoint(b);
	    b = readByte();
	}
	return sb.toString();
    }

    public int nextInt() {
	return (int) nextLong();
    }

    public long nextLong() {
	if (!hasNext())
	    throw new NoSuchElementException();
	long n = 0;
	boolean minus = false;
	int b = readByte();
	if (b == '-') {
	    minus = true;
	    b = readByte();
	}
	if (b < '0' || '9' < b) {
	    throw new NumberFormatException();
	}
	while (true) {
	    if ('0' <= b && b <= '9') {
		n *= 10;
		n += b - '0';
	    } else if (b == -1 || !isPrintableChar(b)) {
		return minus ? -n : n;
	    } else {
		throw new NumberFormatException();
	    }
	    b = readByte();
	}
    }
}