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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;

public class X {

	public static void main(String args[]) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		int t = s.nextInt();

		String s1 = s.next();
		String s2 = s.next();

		char c[] = new char[n];
		int pk = -1;

		HashSet<Integer> hs = new HashSet<Integer>();
		HashSet<Integer> hs2 = new HashSet<Integer>();
		int diff = 0;
		boolean first = true;

		for (int i = 0; i < n; i++) {
			if (s1.charAt(i) == s2.charAt(i)) {
				c[i] = s1.charAt(i);
				hs.add(i);
			} else {
				if (pk == -1)
					pk = i;
				else
					hs2.add(i);

				diff++;

				if (first) {

					first = false;
					c[i] = s1.charAt(i);
				} else {
					first = true;
					c[i] = s2.charAt(i);
				}
			}
		}

		if (diff / 2 + diff % 2 > t) {
			System.out.println(-1);
			return;
		}

		if (diff % 2 == 1) {

			for (int j = 'a'; j <= 'a' + 'z'; j++)
				if (s1.charAt(pk) == j || s2.charAt(pk) == j)
					continue;
				else {
					c[pk] = (char) j;
					break;
				}
		}

		t -= (diff / 2 + diff % 2);

		// System.out.println(c);

		for (int i : hs) {

			if (t == 0)
				break;

			if (c[i] == 'a')
				c[i] = 'b';
			else
				c[i] = 'a';

			t--;
		}

		// System.out.println(c);
		t *= 2;
		if (t > 0) {

			if (diff % 2 == 0)
				hs2.add(pk);

			for (int x : hs2) {

				if (t == 0)
					break;

				for (int j = 'a'; j <= 'a' + 'z'; j++) {
					if (s1.charAt(x) == j || s2.charAt(x) == j)
						continue;
					else {
						c[x] = (char) j;
						t--;
						break;
					}

				}
			}

		}

		System.out.println(c);

	}
}