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

public class main
{
	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		
		int n = s.nextInt();
		int t = s.nextInt();
		
		int last=2;
		String s1 = s.next();
		String s2 = s.next();
		
		char[] a = new char[n];
		
		int la=-1;
		int sl=-1;
		int c=0;
		for(int y=0;y<n;y++)
		{
			if(s1.charAt(y)!=s2.charAt(y))
			{
				sl=la;
				la=y;
				c++;
			}
		}
		
		for(int y=0;y<=(c%2==0?la:sl);y++)
		{
			if(s1.charAt(y)!=s2.charAt(y))
			{
				if(last==2)
				{
					a[y]=s2.charAt(y);
					last=1;
				}
				else
				{
					a[y]=s1.charAt(y);
					last=2;
					t--;
					if(t<0)
					{
						System.out.println("-1");
						return;
					}
				}
			}
			else
				a[y]=s1.charAt(y);
		}
		
		for(int y=(c%2==0?la:sl)+1;y<n;y++)
		{
			if(s1.charAt(y)!=s2.charAt(y))
			{
				char g='a';
				while(g==s1.charAt(y)||g==s2.charAt(y))
					g++;
				a[y]=g;
				t-=1;
				
				if(t<0)
				{
					System.out.println("-1");
					return;
				}
			}
			else
				a[y]=s1.charAt(y);
		}
		
		if(t==0)
		{
			System.out.println(String.valueOf(a));
		}
		else
		{
			for(int y=0;y<n;y++)
			{
				if(s1.charAt(y)==s2.charAt(y))
				{
					char g='a';
					while(g==s1.charAt(y)||g==s2.charAt(y))
						g++;
					a[y]=g;
					t--;
					if(t==0)
					{
						System.out.println(String.valueOf(a));
						return;
					}
				}
			}
			for(int y=0;y<=(c%2==0?la:sl);y++)
			{
				if(s1.charAt(y)!=s2.charAt(y) && s1.charAt(y)==a[y])
				{
					char g='a';
					while(g==s1.charAt(y) || g==s2.charAt(y))
						g++;
					a[y]=g;
					t--;
					if(t==0)
					{
						System.out.println(String.valueOf(a));
						return;
					}
				}
				else if(s1.charAt(y)!=s2.charAt(y) && s2.charAt(y)==a[y])
				{
					char g='a';
					while(g==s2.charAt(y) || g==s1.charAt(y))
						g++;
					a[y]=g;
				}
			}
			
			
		}
	}
}