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.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

public class C {

	static Random rand = new Random();
	static int n, t;
	static char[] a, b;

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

		int[] nt = readIntArray();
		n = nt[0];
		t = nt[1];
		a = br.readLine().toCharArray();
		b = br.readLine().toCharArray();

		int eqCnt = 0;
		int uneqCnt = 0;
		boolean[] eq = new boolean[n];
		for (int i = 0; i < eq.length; i++) {
			eq[i] = a[i] == b[i];
			if (eq[i]) {
				eqCnt++;
			} else {
				uneqCnt++;
			}
		}

		if (2 * t < uneqCnt) {
			System.out.println("-1");
			return;
		} else {
			char[] c = new char[n];

			if (uneqCnt >= t && uneqCnt <= 2 * t) {
				int both = 2 * t - uneqCnt;
				int single = (uneqCnt - both) / 2;
				int ta = single, tb = single;

				for (int i = 0; i < eq.length; i++) {
					if (!eq[i]) {
						if (both > 0) {
							c[i] = diffboth(a, b, i);
							both--;
						} else if (ta > 0) {
							c[i] = a[i];
							ta--;
						} else {
							c[i] = b[i];
							tb--;
						}
					} else {
						c[i] = b[i];
					}
				}
			} else {
				for (int i = 0; i < eq.length; i++) {
					if (!eq[i]) {
						c[i] = diffboth(a, b, i);
						t--;
					}
				}
				
				for (int i = 0; i < eq.length; i++) {
					if (eq[i]) {
						if (t > 0) {
							c[i] = diffboth(a, b, i);
							t--;
						} else {
							c[i] = a[i];
						}	
					}
				}
			}

			System.out.println(new String(c));
		}

	}

	private static char diffboth(char[] a2, char[] b2, int i) {
		for (int j = 0; j < 26; j++) {
			char c = (char)(j + 'a');
			if (c != a2[i] && c != b2[i]) {
				return c;
			}
		}
		
		return '!';
	}

	static void print(int[] a) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < a.length; i++) {
			if (sb.length() > 0) {
				sb.append(' ');
			}

			sb.append(a[i]);
		}

		System.out.println(sb);
	}

	static class ReverseComparator implements Comparator<Integer> {

		@Override
		public int compare(Integer arg0, Integer arg1) {
			return -arg0.compareTo(arg1);
		}

	}

	static void inc(HashMap<Integer, Integer> map, int key, int val) {
		if (!map.containsKey(key)) {
			map.put(key, val);
		} else {
			map.put(key, map.get(key) + val);
		}
	}

	static void inc(HashMap<Integer, Integer> map, int key) {
		inc(map, key, 1);
	}

	static int gcd(int a, int b) {

		if (a < b)
			return gcd(b, a);

		do {
			// a = gcd * z * x + y
			// b = gcd * z
			int t = a % b;
			a = b;
			b = t;
		} while (b > 0);

		return a;
	}

	static void shuffle(List<Integer> a) {
		for (int i = 0; i < a.size(); i++) {
			int j = rand.nextInt(a.size() - i);
			swap(a, i, i + j);
		}
	}

	static void swap(List<Integer> a, int i, int j) {
		int x = a.get(i);
		a.set(i, a.get(j));
		a.set(j, x);
	}

	static void append(StringBuilder sb, int val) {
		if (sb.length() > 0) {
			sb.append('\n');
		}

		sb.append(val);
	}

	static InputStreamReader isr = new InputStreamReader(System.in);
	static BufferedReader br = new BufferedReader(isr);
	static StringBuilder sb = new StringBuilder();

	static String readNextToken() throws IOException {
		sb.setLength(0);
		char c = ' ';
		do {
			c = ((char) br.read());
			if (Character.isWhitespace(c)) {
				if (sb.length() > 0) {
					break;
				}
			} else {
				sb.append(c);
			}
		} while (true);

		return sb.toString();
	}

	static int ni() throws Exception {
		return Integer.parseInt(readNextToken());
	}

	static long nl() throws Exception {
		return Long.parseLong(readNextToken());
	}

	static int[] readIntArray() throws IOException {

		String[] v = br.readLine().split(" ");
		int[] ans = new int[v.length];

		for (int i = 0; i < ans.length; i++) {
			ans[i] = Integer.valueOf(v[i]);
		}

		return ans;
	}

	static long[] readLongArray() throws IOException {
		String[] v = br.readLine().split(" ");
		long[] ans = new long[v.length];

		for (int i = 0; i < ans.length; i++) {
			ans[i] = Long.valueOf(v[i]);
		}

		return ans;
	}

	static <T> void print(List<T> v) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < v.size(); i++) {
			if (sb.length() > 0) {
				sb.append(' ');
			}

			sb.append(v.get(i));
		}

		System.out.println(sb);
	}
}