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.io.Reader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Problem3 {
	public static void main(String[] args) {
		Scanner input = new Scanner();
		int n = input.nextInt();
		int difference = input.nextInt();
		String s1 = input.readNextLine();
		String s2 = input.readNextLine();
		if(difference > n){
			System.out.println(-1);
			return;
		}
		int sharedCharacters = getNumSharedCharacters(s1, s2);
		int minDiff = (int)(((n - sharedCharacters)/2.0) + .51);
		if(difference < minDiff){
			System.out.println(-1);
			return;
		}

		int splitCharacters = n-sharedCharacters;
		StringBuilder answer = new StringBuilder();
		int equals = difference - splitCharacters;
		if(equals < 0){
			equals = 0;
		}
		int currentEquals = 0;

		int bothMax = 2 * difference - splitCharacters;
		int leftMax = difference - bothMax;
		int rightMax = difference - bothMax;
		int left = 0;
		int right = 0;
		int both = 0;
		for(int a = 0; a < n; a++){
			if(s1.charAt(a) == s2.charAt(a)){
				if(currentEquals < equals){ //handles the case we must use the equal elements of strings
					currentEquals++;
					answer.append(getDifferentChar(s1.charAt(a), s2.charAt(a)));
				}
				else{
					answer.append(s1.charAt(a));
				}
			}
			else{ //if not, we can just use the normal elements.
				if(both < bothMax){
					both++;
					answer.append(getDifferentChar(s1.charAt(a), s2.charAt(a)));
				}
				else if(left < leftMax){
					left++;
					answer.append(s1.charAt(a));
				}
				else if(right < rightMax){
					right++;
					answer.append(s2.charAt(a));
				}
			}
		}
		System.out.println(answer);
	}

	private static int getNumSharedCharacters(String s1, String s2) {
		int count = 0;
		for(int a = 0; a < s1.length(); a++){
			if(s1.charAt(a) == s2.charAt(a)){
				count++;
			}
		}
		return count;
	}
	public static char getDifferentChar(char a, char b){
		if(a != 'a' && b != 'a'){
			return 'a';
		}
		if(a != 'b' && b != 'b'){
			return 'b';
		}
		return 'c';		
	}
	//////Fastscanner class.
	public static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		public Scanner(Reader in) {
			br = new BufferedReader(in);
		}

		public Scanner() {
			this(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

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

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

		double nextDouble() {
			return Double.parseDouble(next());
		}

		// Slightly different from java.util.Scanner.nextLine(),
		// which returns any remaining characters in current line,
		// if any.
		String readNextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}

}