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.*;
import java.util.*;

public class K {

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

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int t = sc.nextInt();



		char[] s1 = sc.next().toCharArray();
		char[] s2 = sc.next().toCharArray();

		int same1 = 0;
		int same2 = 0;
		
		HashSet<Integer> set1 = new HashSet<>();
		HashSet<Integer> set2 = new HashSet<>();
		
		
		
		
		char [] s3 = new char[n];
		
		for (int i = 0; i < n && same1 < n-t & same2 < n-t; i++) {
			if(s1[i] == s2[i])
			{
				
				same1++;
				same2++;
				s3[i] = s1[i];
				set1.add(i);
				set2.add(i);
				
				
			}
		}
		
		for(int i = 0 ; i < n && same1 < n-t ; i++)
		{
			if(!set1.contains(i) && !set2.contains(i))
			{
				s3[i] = s1[i];
				
				set1.add(i);
				same1++;
				
			}
		}
		
		if(same1 != n-t) {System.out.println(-1); return ;}
		
		for(int i = 0 ; i < n && same2 < n-t ; i++)
		{
			if(!set1.contains(i) && !set2.contains(i))
			{
				s3[i] = s2[i];
				
				set2.add(i);
				same2++;
				
			}
		}
		
		if(same2 != n-t) {System.out.println(-1); return ;}
		
		
		for(int i = 0 ; i < n ; i++)
		{
			if(!set1.contains(i) && !set2.contains(i))
			{
				Character ch = null ;
				for(char c = 'a' ; c<='z' ; c++)
				{
					if(s1[i] != c && s2[i] != c )
					{
						
						ch = c ;
						break;
					}
					
				}
				
				if(ch == null) {
					System.out.println(-1);
					
					return;
				}
				
				s3[i] = ch;
			}
		}
		
		System.out.println(s3);

		
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

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

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

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

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

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

}