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:
//package com.company;

//import java.io.file.Paths;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        // write your code here
        Scanner s = new Scanner(System.in);
    int n=s.nextInt();int p=s.nextInt();
    char[] a=s.next().toCharArray();
     char[] b=s.next().toCharArray();
     char[] c=new char[n];
     int count=0;HashMap<Integer,Integer> j=new HashMap<Integer, Integer>();
     for(int i=0;i<a.length;i++){
         if(a[i]==b[i]){
          count++;  // j.put(i,1);
         }
     }int flag=0;
  if(count>=n-p){
         int d=0;
         for(int i=0;i<n;i++){//System.out.println(" "+a[i]+" "+b[i]+" "+count+" "+(n-p));
             if(a[i]==b[i]&&d<n-p){
                 c[i]=a[i];d++;}
                else {
                 char h='a';
                 while(h==a[i]||h==b[i]) h++;

                 c[i]=h;

             }}
         }else{
         if(2*(n-p-count)<=n-count){
             for(int i=0;i<n;i++){
                 if(a[i]==b[i]) c[i]=a[i];
             }
             int ca=0;int cb=0;
             for(int i=0;i<n;i++){
                 if(a[i]!=b[i]){
                     if(ca<n-p-count){
                         c[i]=a[i];ca++;
                     }else if(cb<n-p-count){
                         c[i]=b[i];cb++;
                     }else{
                         char h='a';
                         while(h==a[i]||h==b[i]) h++;
                         c[i]=h;
                     }
                 }
             }
         }else {flag=1;System.out.println(-1);}

  }if(flag==0){
         for(int i=0;i<n;i++){
             System.out.print(c[i]);
         }
        }
    }

}