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.IOException;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {

	
	public static void main(String[] args)
	{
    	
		FasterScanner s=new FasterScanner();
		PrintWriter out=new PrintWriter(System.out);
		
		int n=s.nextInt();
		int t=s.nextInt();
		
		char[] a=s.nextLine().toCharArray();
		char[] b=s.nextLine().toCharArray();
		char[] c=new char[a.length];
		int count=0;
		for(int i=0;i<a.length;i++)
		{
			if(a[i]==b[i])
			{
				c[i]=a[i];
				count++;
			}
		}
		
		int t1=t;
		int t2=t;
		count=n-count;
		int x=2*t-count;
		int i=0;
		if(x<0)
		{
			System.out.println(-1);
			return;
			
		}
		for(i=0;i<n&&x>0;i++)
		{
			if(a[i]!=b[i])
			{
				for(int j='a';j<='z';j++)
						if(a[i]!=j && b[i]!=j)
						{
							c[i]=(char) j;
							x--;
							t--;
							break;
						}
			}
		}
//		System.out.println("noe");
		t1=t;
		t2=t;
		while(i<n && (t1>0 || t2>0))
		{
			if(c[i]==0)
			{
				if(t1>t2)
				{
					c[i]=a[i];
					t1--;
				}
				else
				{
					c[i]=b[i];
					t2--;
				}
			}
			i++;
		}
//		System.out.println("noe");
		if(t1!=t2)
		{
			System.out.println(-1);
			return;
		}
		for(i=0;i<n && t1>0;i++)
		{
			if(a[i]==b[i])
			{
				if(c[i]=='z')
					c[i]='a';
				else
					c[i]='z';
				t1--;
				
			}
			
		}
//		System.out.println("nowe"+t1);
		if(t1==0)
		System.out.println(new String(c));
		else
		System.out.println(-1);
	}


	public  static class SegTree {
	
		static int n;
		static long[] t;
		SegTree(int n)
		{
			this.n=n;
			t=new long[2*n];
			build();
		}
		
		void build() {  // build the tree
			for(int i=n;i<2*n;i++)
				t[i]=Long.MAX_VALUE;
			for (int i = n - 1; i > 0; --i)
				t[i]=Math.min(t[i<<1],t[i<<1|1]);
		}
	
		void modify(int l, int r, int value) {
			  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			    if ((l&1)!=0) t[l++] = Math.min(t[l],value);
			    if ((r&1)!=0) t[--r] = Math.min(t[r],value);
			  }
			}
		
			long query(int p) {
			  long res = Long.MAX_VALUE;
			  for (p += n; p > 0; p >>= 1) res=Math.min(res, t[p]);
			  return res;
			}
	}
	
	

	static int[] sieveEratosthenes(int n) {
		if(n <= 32){
			int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
			for(int i = 0;i < primes.length;i++){
				if(n < primes[i]){
					return Arrays.copyOf(primes, i);
				}
			}
			return primes;
		}

		int u = n + 32;
		double lu = Math.log(u);
		int[] ret = new int[(int) (u / lu + u / lu / lu * 1.5)];
		ret[0] = 2;
		int pos = 1;

		int[] isp = new int[(n + 1) / 32 / 2 + 1];
		int sup = (n + 1) / 32 / 2 + 1;

		int[] tprimes = { 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
		for(int tp : tprimes){
			ret[pos++] = tp;
			int[] ptn = new int[tp];
			for(int i = (tp - 3) / 2;i < tp << 5;i += tp)
				ptn[i >> 5] |= 1 << (i & 31);
			for(int i = 0;i < tp;i++){
				for(int j = i;j < sup;j += tp)
					isp[j] |= ptn[i];
			}
		}

		// 3,5,7
		// 2x+3=n
		int[] magic = { 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4,
				13, 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14 };
		int h = n / 2;
		for(int i = 0;i < sup;i++){
			for(int j = ~isp[i];j != 0;j &= j - 1){
				int pp = i << 5 | magic[(j & -j) * 0x076be629 >>> 27];
				int p = 2 * pp + 3;
				if(p > n)
					break;
				ret[pos++] = p;
				for(int q = pp;q <= h;q += p)
					isp[q >> 5] |= 1 << (q & 31);
			}
		}

		return Arrays.copyOf(ret, pos);
	}
	 static int gcd (long m, long n){
         long x;
         long y;
         while(m%n != 0){
     		x = n;
     		y = m%n;
     		m = x;
     		n = y;
         }
         return (int) n;
     }
	
	static long mod=(long) (1e9+7);
	static long pow(long a,long p)
	{
		if(p==0)
			return 1;
		if(p==1)
			return a;
		long ans=1;
		ans=pow(a,p/2);
		ans*=ans;
		ans%=mod;
		if(p%2!=0)
			ans*=a;
		ans%=mod;
		return ans;
	}
	

//	static void go(int ind)
//	{
//		int count=0;
//		done[ind]=true;
//		for(int i=0;i<n;i++)
//		{
//			if(edge[ind][i])
//				count++;
//		}
//		if(count>2)
//		{
//			System.out.println("NO");
//			System.exit(0);
//		}
//		if(count==2)
//		{
//			int left=0;
//			int right=0;
//			for(int i=0;i<n;i++)
//			{
//				if(edge[ind][i])
//				{
//					left=i;
//				}
//			}
//			for(int i=left+1;i<n;i++)
//			{
//				if(edge[ind][i])
//				{
//					right=i;
//				}
//			}
//			done[left]=true;
//			done[right]=true;
//			
//			
//			
//			
//		}
//	}
//	
//	
//    static void dfs(int ind)
//    {
//    	started[ind]=true;
//    	for(int i=0;i<n;i++)
//    	{
//    		if(edge[ind][i])
//    		{
//    			if(done[i])
//    			{
//    				System.out.println("NO");
//    				System.exit(0);
//    			}
//    			if(!started[i])
//    				dfs(i);
//    		}
//    	}
//    	done[ind]=true;
//    }

	public static class Pair
	{
		int x;
		int y;
		public Pair(int x,int y)
		{
			this.x=x;
			this.y=y;
			
		}
	}
	

	
	
	
	
	
	
	
	
	
	
























    
    public static class FasterScanner {
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = System.in.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        public String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
           
        public int[] nextIntArray(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }
       
        public long[] nextLongArray(int n) {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextLong();
            }
            return arr;
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
    }
}