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.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class C {
	
	public static char diff_char(final char a, final char b){
		for(char c = 'a'; c <= 'z'; c++){
			if(c != a && c != b){
				return c;
			}
		}
		
		return '\0';
	}
	
	public static boolean is_valid(char[] a){
		for(final char c : a){
			if(c == '\0'){
				return false;
			}
		}
		
		return true;
	}
	
	public static int check_diff(final int n, final char[] a, final char[] b){
		int count = 0;
		for(int i = 0; i < n; i++){
			if(a[i] != b[i]){
				count++;
			}
		}
		
		return count;
	}
	
	public static void main(String[] args) {

		try (final Scanner sc = new Scanner(System.in)) {
			final int len = sc.nextInt();
			final int t = sc.nextInt();	
			
			final String s1_str = sc.next();
			final String s2_str = sc.next();
			char[] s1 = s1_str.toCharArray();
			char[] s2 = s2_str.toCharArray();
			
			int both = 0, either = 0;
			for(int i = 0; i < len; i++){
				if(s1[i] == s2[i]){
					both++;
				}else{
					either++;
				}
			}
			
			if(t == 0){
				if(both == len){
					System.out.println(s1);
				}else{
					System.out.println(-1);
				}
			
				return;
			}
			
			char[] answer = new char[len];
			boolean force_use = either % 2 != 0;
			int g_count = 0;
			
			if(force_use){
				for(int i = 0; i < len; i++){
					if(s1[i] != s2[i]){
						g_count++;
						answer[i] = diff_char(s1[i], s2[i]);
						break;
					}
				}
			}
			
			//System.out.println(either + " " + t);
			final int forced_t = t - (force_use ? 1 : 0);
			final int forced_either = either - (force_use ? 1 : 0);
			
			final int either_either_diff = Math.max(0, forced_either - forced_t);
			final int either_both_diff = forced_either - either_either_diff * 2;
			//System.out.println(either_either_diff + " " + either_both_diff);
			if(either_both_diff < 0){
				System.out.println(-1);
				return;
			}
			//
			
			
			for(int i = 0, count = 0; i < len && count < either_both_diff; i++){
				if(s1[i] != s2[i] && answer[i] == '\0'){
					count++;
					g_count++;
					answer[i] = diff_char(s1[i], s2[i]);
				}
			}
			
			for(int i = 0, count = 0; i < len && count < either_either_diff; i++){
				if(s1[i] != s2[i] && answer[i] == '\0'){
					count++;
					g_count++;
					answer[i] = s2[i];
				}
			}
			for(int i = 0, count = 0; i < len && count < either_either_diff; i++){
				if(s1[i] != s2[i] && answer[i] == '\0'){
					count++;
					answer[i] = s1[i];
				}
			}
			
			final int both_diff = t - g_count;
			for(int i = 0, count = 0; i < len && count < both_diff; i++){
				if(s1[i] == s2[i] && answer[i] == '\0'){
					count++;
					answer[i] = diff_char(s1[i], s2[i]);
				}
			}
			for(int i = 0; i < len; i++){
				if(s1[i] == s2[i] && answer[i] == '\0'){
					answer[i] = s1[i];
				}
			}
			
			final int s1_diff = check_diff(len, s1, answer);
			final int s2_diff = check_diff(len, s2, answer);
			//System.out.println(Arrays.toString(answer) + " "  + s1_diff + " " + s2_diff);
			if(is_valid(answer) && s1_diff == t && s2_diff == t){
				for(int i = 0; i < len; i++){
					System.out.print(answer[i]);
				}
				System.out.println();
			}else{
				System.out.println(-1);
			}
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() {
			try {
				while (!hasNext()) {
					tok = new StringTokenizer(br.readLine());
				}
			} catch (IOException e) { /* ignore */
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() {
			getLine();
			return tok.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public void close() {
			try {
				br.close();
			} catch (IOException e) { /* ignore */
			}
		}
	}
}