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.awt.List;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.*;
public class Watermelon2 {
	public static void main(String[] args) throws IOException{
		Main2 m=new Main2();
		m.solve();
	}
	}
class Main2{
	
	 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	 private int[] array;
	    private int[] tempMergArr;
	    private int length;
	
	    BigInteger[] temp=new BigInteger[31];
		BigInteger x,y,z;
	    StringTokenizer stringTokenizer;

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

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

	    long nextLong() throws IOException {
	        return Long.parseLong(next());
	    }
	    int marr[]=null;
	    void solve() throws IOException  {
	    	      int n=this.nextInt(),t=this.nextInt();
	    	      String x=this.next();
	              String y=this.next();
	              char[] sarr=x.toCharArray();
	              char[] tarr=y.toCharArray();
	              char[] rarr=new char[n];
	              int temp=n-t;
	              for(int i=0;i<n;i++)
	            	  rarr[i]='!';
	        //      display(rarr);
                  for(int i=0;i<n;i++)
                	  if(sarr[i]==tarr[i]&&temp>0)
                		  {rarr[i]=sarr[i];temp--;}
                  
             A:     for(int i=0;i<n;i++){
            	    if(temp==0)
            	    	break;
            	      while(rarr[i]!='!')
          	    	  {
            	    	  i++;
            	    	  if(i==n)
            	    		  break A;
          	    	  }
          	         if(i==n)
          	    	  break;
          	        
            	    if(rarr[i]=='!'){
                		  rarr[i]=sarr[i];
                		  
                	 }
            	      i++;
            	      if(i==n)
            	    	  break;
            	      while(rarr[i]!='!')
            	      {
            	    	  i++;
            	    	  if(i==n)
            	    		  break A;
            	      }
            	      if(i==n)
            	    	  break;
            	      if(rarr[i]=='!'){
                		  rarr[i]=tarr[i];
                		
                	 }
                	temp--;
                  }
               // 		  display(rarr);
                for(int i=0;i<n;i++){
                	if(rarr[i]=='!'){
                		//System.out.println((tarr[i]-0)+" "+(sarr[i]-0));
                		int k=sarr[i]+tarr[i];
                		//System.out.println(((tarr[i]+sarr[i])/2)+" "+(k/2));
                		if(((tarr[i]+sarr[i])/2)!=tarr[i]&&((tarr[i]+sarr[i])/2)!=sarr[i]){
                			rarr[i]=(char)((tarr[i]+sarr[i])/2);
                			//System.out.println((char)((tarr[i]+sarr[i])/2)+" "+tarr[i]+" "+sarr[i]);
                		}
                		else
                			{
                			rarr[i]=(char)(((tarr[i]+sarr[i])/2)+2);
                			if(rarr[i]>'z')
                				rarr[i]='a';
                			}
                	}
                }
                int xount=0,yount=0;
                for(int i=0;i<n;i++){
                	if(sarr[i]!=rarr[i])
                		xount++;
                	if(tarr[i]!=rarr[i])
                		yount++;
                }
                if(yount==t&&xount==t)
          		  display(rarr);
                else
                	System.out.println(-1);
	    }
	    
	    public String recurs(char[] carr,int k){
	    	int count=0;
	    	for(int i=0;i<carr.length;i++){
	    		if(i+k-1<carr.length)
	    		if(carr[i]=='-'){
	    			for(int j=i;j<i+k;j++){
	    				
	    				if(carr[j]=='+')
	    					{carr[j]='-';continue;}
	    				if(carr[j]=='-')
	    					{carr[j]='+';continue;}
	    		//		System.out.println(j+" "+i+" "+carr[j]);
	    			}
	    			count++;
	    			
	    		}
	    	//	display(carr);
	    	}
	    	for(int i=0;i<carr.length;i++){
	    		if(carr[i]=='-')
	    			return "IMPOSSIBLE";
	    	}
	    	return Integer.toString(count);
	    }
	    static int max_LIS=0;
	    public int LIS(int[] arr,int n){
	    	if(n==0)
	    		{
	    		marr[0]=1;
	    		return 1;
	    		}
	    	
	    	int current =1;
	    	for(int i=0;i<n;i++){
	    		int subproblem=0;
	    		if(marr[i]==0)
	    		{
	    			subproblem=LIS(arr,i);
	    			marr[i]=subproblem;
	    		}
	    		else{
	    		//	System.out.println("Hey");
	    			subproblem=marr[i];
	    		}
	    		
	    		System.out.println(current+" "+subproblem+" "+i);
	    		if(arr[i]<arr[n]&&current<(1+subproblem)){
	    			current=(1+subproblem);
	    		}
	    	}
	    	if(max_LIS<current)
	    		max_LIS=current;
	    	return current;
	    }
	    
	public BigInteger comb(int n,int r){
	     x=this.temp[n];
		 y=this.temp[r];
		 z=this.temp[n-r];
	//	 System.out.println(x+" "+y+" "+z);
		 BigInteger ret=x.divide(y.multiply(z));
		 return ret;
		 
	}
	public void fact(){
		this.temp[0]=BigInteger.ONE;
		this.temp[1]=BigInteger.ONE;
		for(int i=2;i<this.temp.length;i++){
			temp[i]=(temp[i-1].multiply(BigInteger.valueOf(i)));
		}
	}
	private static int gcd(int a, int b)
	{
	    while (b > 0)
	    {
	    	int temp = b;
	        b = a % b; // % is remainder
	        a = temp;
	    }
	    return a;
	}
	private static int lcm(int a, int b)
	{
	    return a * (b / gcd(a, b));
	}
	static int[] toFractionPos(int x,int y){
		int a=gcd(x,y);
		int[] arr={x/a,y/a};
		//display(arr);
		return arr;
	}
   
	static void display(double[][] arr){
		
		for(int i=0;i<arr.length;i++){
			for(int j=0;j<arr[i].length;j++){
				System.out.print(arr[i][j]+" ");
		}
		System.out.println();
		}
	System.out.println();
	}

	 static void display(String[] arr){
			for(int i=0;i<arr.length;i++){
				System.out.println(arr[i]+" ");
			}	
			//System.out.println();
		
	 }
	 static void display(long[] arr){
		 for(int i=0;i<arr.length;i++)
				System.out.print(arr[i]+" ");
		System.out.println();
		 }
		 static void display(double[] arr){
		 	   for(int i=0;i<arr.length;i++){
		 		   System.out.print(arr[i]+" ");
		 	   }
		 	   System.out.println();
	    }
	 static void display(char[] arr){
		// System.out.println();
		 int t=0;
			for(int i=0;i<arr.length;i++){
				if(arr[i]!='0'){t=i;break;}
			}	
			while(t!=arr.length){
				System.out.print(arr[t]);
				t++;
			}
			System.out.println();
		
		  }
	 static String str(char[] carr){
		 String str="";
		 for(int i=0;i<carr.length;i++){
			    str=str+carr[i];
			}
		 return str;
	 }
	    public void sort(int inputArr[]) {
	        this.array = inputArr;
	        this.length = inputArr.length;
	        this.tempMergArr = new int[length];
	        doMergeSort(0, length - 1);
	    }
	 
	    private void doMergeSort(int lowerIndex, int higherIndex) {
	         
	        if (lowerIndex < higherIndex) {
	            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
	            // Below step sorts the left side of the array
	            doMergeSort(lowerIndex, middle);
	            // Below step sorts the right side of the array
	            doMergeSort(middle + 1, higherIndex);
	            // Now merge both sides
	            mergeParts(lowerIndex, middle, higherIndex);
	        }
	    }
	 
	    private void mergeParts(int lowerIndex, int middle, int higherIndex) {
	 
	        for (int i = lowerIndex; i <= higherIndex; i++) {
	            tempMergArr[i] = array[i];
	        }
	        int i = lowerIndex;
	        int j = middle + 1;
	        int k = lowerIndex;
	        while (i <= middle && j <= higherIndex) {
	            if (tempMergArr[i] <= tempMergArr[j]) {
	                array[k] = tempMergArr[i];
	                i++;
	            } else {
	                array[k] = tempMergArr[j];
	                j++;
	            }
	            k++;
	        }
	        while (i <= middle) {
	            array[k] = tempMergArr[i];
	            k++;
	            i++;
	        }
	 
	    }
}


 class  Count2 implements Comparable {
    	    Integer i;
    	    Integer j;
            Integer k;
    	    Count2(int i,int j){
    	        this.j=j;
    	        this.i=i;
    	        this.k=i;
    	    }
    	    void display(){
    	    	System.out.println(i+" "+j+" "+k);
    	    }
    	    
    	    	@Override
    		public int compareTo(Object o) {
    			// TODO Auto-generated method stub
    			Count2 c=(Count2)o;
    			if(i.compareTo(c.i)>0)
    				return 1;
    			else if(i.compareTo(c.i)<0)
    				return -1;
    			else{
    				return 0;
    				
    			}
    		}
    		
    	}

 class  Counti2 implements Comparable {
    	    Integer i;
    	    int j;
    	    int k;
    	    Counti2(int i,int j,int k){
    	        this.j=j;
    	        this.i=i;
    	        this.k=k;
    	    }
    	    void display(){
    	    	System.out.println(i+" "+j+" "+k);
    	    }
    	    
    	    	@Override
    		public int compareTo(Object o) {
    			// TODO Auto-generated method stub
    			Counti2 c=(Counti2)o;
    			if(i.compareTo(c.i)>0)
    				return 1;
    			else if(i.compareTo(c.i)<0)
    	    		return -1;
    			else
    				return 0;
    		}
    		
    	}
		
 class Extra2{
	 ArrayList<Integer> list=new ArrayList<>();
	 Extra2(int i){
		 list.add(i);
	 }
	 void display(){
		 System.out.println(list.size());
		 for(int i=0;i<list.size();i++){
			 System.out.print(list.get(i)+" ");
		 }
		 System.out.println();
	 }
 }