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.lang.*;
import java.io.*;
public class SolutionC {

    /**
     * @param args
     */
    
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int n = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        String s1 = br.readLine();
        String s2 = br.readLine();
        int countSame = 0;
        char [] s3 = new char[s1.length()];
        for(int i =0; i<s1.length(); i++){
            if(s1.charAt(i) == s2.charAt(i)){
                countSame++;
                s3[i] = s1.charAt(i);
            }
        }
        int countDiff = s1.length()-countSame;
        if(t>countDiff){
            if(t-countDiff > countSame){
                System.out.println("-1");
                return;
            }else{
                for(int i=0; i<s1.length();i++){
                    if(s1.charAt(i)!=s2.charAt(i)){
                        char k = 'a';
                        while(k == s1.charAt(i) || k == s2.charAt(i)) k++;
                        s3[i] = k;
                    }
                }
                t = t-countDiff;
                for(int i=0;i<s1.length() && t>0;i++){
                    if(s1.charAt(i)==s2.charAt(i)){
                        if(s1.charAt(i)!='z') s3[i] = (char)(s1.charAt(i)+1);
                        else s3[i] = 'a';
                        t--;
                    }
                }
                for(int i=0;i<s1.length();i++) System.out.print(s3[i]);
                System.out.println();
            }
        }else if(t == countDiff){
            for(int i=0; i<s1.length(); i++){
                if(s1.charAt(i) != s2.charAt(i)){
                    char k = 'a';
                    while(k == s1.charAt(i) || k == s2.charAt(i)) k++;
                    s3[i] = k;
                }
            }
            for(int i=0;i<s1.length();i++) System.out.print(s3[i]);
            System.out.println();
        }else{
            int countDiffMax = countDiff;
            int countDiffMin = (countDiff+1)/2;
            if(t>=countDiffMin){
                if(countDiff%2 == 0){
                    int x = (t-countDiffMin)*2;
                    int i;
                    for(i=0; i < s1.length() && x>0; i++){
                        if(s1.charAt(i) != s2.charAt(i)){
                            x--;
                            char k = 'a';
                            while(k == s1.charAt(i) || k == s2.charAt(i)) k++;
                            s3[i] = k;
                        }
                    }
                    boolean isS1 = true;
                    while(i<s1.length()){
                        if(s1.charAt(i) != s2.charAt(i)){
                            if(isS1){
                                s3[i] = s1.charAt(i);
                                isS1 = (!isS1);
                            }else{
                                s3[i] = s2.charAt(i);
                                isS1 = (!isS1);
                            }
                        }
                        i++;
                    }
                    for(int j=0;j<s1.length();j++) System.out.print(s3[j]);
                    System.out.println();
                }else if(countDiff %2 == 1){
                    int x = (t-countDiffMin)*2 + 1;
                    int i;
                    for(i=0; i < s1.length() && x>0; i++){
                        if(s1.charAt(i) != s2.charAt(i)){
                            x--;
                            char k = 'a';
                            while(k == s1.charAt(i) || k == s2.charAt(i)) k++;
                            s3[i] = k;
                        }
                    }
                    boolean isS1 = true;
                    while(i<s1.length()){
                        if(s1.charAt(i) != s2.charAt(i)){
                            if(isS1){
                                s3[i] = s1.charAt(i);
                                isS1 = (!isS1);
                            }else{
                                s3[i] = s2.charAt(i);
                                isS1 = (!isS1);
                            }
                        }
                        i++;
                    }
                    for(int j=0;j<s1.length();j++) System.out.print(s3[j]);
                    System.out.println();
                }
            }else{
                System.out.println("-1");
            }
        }
    }

}