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 CodeForces.Round324;

import java.util.*;

/**
 * Created by Ilya Sergeev on 06.10.2015.
 */
public class Cs1s2 {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Character> alphabet = new ArrayList<>();
        for (int i = 'a'; i < 'a'+26; i++) {
            alphabet.add(((char) i));
        }
        int n = sc.nextInt();
        int t = sc.nextInt();
        String a = sc.next();
        String b = sc.next();
        TreeMap<Character, Integer> map = new TreeMap();
        char[] as = new char[n];
        char[] bs = new char[n];
        as = a.toCharArray();
        bs = b.toCharArray();
        int k = 0;
        char[] out = new char[n];
        for (int i = 0; i < n && k < n-t; i++) {
            if(as[i] == bs[i]){
                out[i] = as[i];
                k++;
            }
        }
        int t1 = n - t - k, t2 = n - t - k;
        if (k < n - t){

            for (int i = 0; i < n && (t1 != 0 || t2 != 0); i++) {
                if (out[i] == '\u0000' && t1 >=t2){
                    out[i] = as[i];
                    t1--;
                    k++;
                }
                else if(out[i] == '\u0000' && t2 > t1){
                    out[i] = bs[i];
                    t2--;
                    k++;
                }
            }
        }
        if(t1 != 0 || t2 != 0){
            System.out.println(-1);
            return;
        }
        for (int i = 0; i < n; i++) {
            if(out[i] == '\u0000') {
                out[i] = alphabet.get(1) != as[i] && alphabet.get(1) != bs[i] ? alphabet.get(1) :
                        alphabet.get(0) != as[i] && alphabet.get(0) != bs[i] ? alphabet.get(0) :
                                alphabet.get(alphabet.size() - 1) != as[i] && alphabet.get(alphabet.size() - 1) != bs[i] ? alphabet.get(alphabet.size() - 1) : ' ';
            }
        }

        if(k >= n - t) System.out.println(String.valueOf(out));
        else System.out.println(-1);
    }

}

/*
*  for (int i = 0; i < n; i++) {
            Character ac = as[i];
            Character bc = bs[i];
            if(map.containsKey(ac))map.put(ac, map.get(ac)+1);
            else map.put(ac,1);
            if(map.containsKey(bc))map.put(bc, map.get(bc)+1);
            else map.put(bc,1);
        }
        StringBuilder sb = new StringBuilder();
        LinkedList<Map.Entry<Character, Integer>> list = new LinkedList<>(map.entrySet());

        Collections.sort(list, new Comparator<Map.Entry<Character, Integer>>() {
            @Override
            public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
                Integer a = o1.getValue();
                Integer b = o2.getValue();
                if(a%2 == 0 && b%2 == 0) return a.compareTo(b);
                if(a%2 != 0 && b%2 == 0) return 1;
                if(a%2 == 0 && b%2 != 0) return -1;
                return a.compareTo(b);
            }
        });
        Iterator<Map.Entry<Character, Integer>> iterator = list.iterator();
        Iterator<Map.Entry<Character, Integer>> iterator2 = list.descendingIterator();
        for (int k = 0; iterator.hasNext() && k < n-t; ) {
            Map.Entry<Character, Integer> entry = iterator.next();
            if(entry.getValue()> 1 && entry.getValue() % 2 == 0) {
                int c = entry.getValue() / 2;
                for (int i = 0; i < c && k < n-t; i++, k++) {
                    sb.append(entry.getKey());
                    entry.setValue(entry.getValue()-2);
                }
            }
            else if(k+2 < n-t && iterator2.hasNext()){
                Map.Entry<Character, Integer> entry2 = iterator2.next();
                if(entry.getValue() % 2 != 0  && a.indexOf(entry.getKey())!=-1 && iterator2.hasNext() ) {
                    Map.Entry<Character, Integer> entry3 = iterator2.next();
                    if(entry3.getValue() % 2 != 0 && b.indexOf(entry2.getKey())!=-1) {
                        sb.append(entry2.getKey());
                        sb.append(entry3.getKey());
                        entry2.setValue(entry2.getValue()-1);
                        entry3.setValue(entry3.getValue()-1);
                    }
                }
            }
}
        outer:
        for (int i = 0; sb.length()< n && i < map.size(); i++) {
        Map.Entry<Character, Integer> entry = list.get(i);
        if(entry.getValue() != 0 && a.indexOf(entry.getKey())!=-1){
        for (int j = 0; j < map.size(); j++) {
        Map.Entry<Character, Integer> entry2 = list.get(j);
        if(entry2.getValue() != 0 && b.indexOf(entry2.getKey())!=-1){
        sb.append(entry.getKey());
        sb.append(entry2.getKey());
        entry2.setValue(entry2.getValue()-1);
        entry.setValue(entry.getValue()-1);
        continue outer;
        }
        }
        }
        }
        alphabet.removeAll(map.keySet());
        boolean noMore = false;
        Iterator<Character> iter = alphabet.iterator();
        for (int i = 0, j = 0;sb.length()+i<=n && i < t; i++) {
            if(!noMore) {
                for (Map.Entry<Character, Integer> entry : map.entrySet()) {
                    if (entry.getValue() % 2 != 0 && entry.getValue() > 1 && sb.length()+i<=n) {
                        sb.append(entry.getKey());
                        entry.setValue(entry.getValue() - 1);
                        break;
                    }
                    j++;
                }
            }
            if(j == map.size())noMore = true;
            if(iter.hasNext()) {
                sb.append(iter.next());
                iter.remove();
            }
        }
        if(sb.length() < n) System.out.println(-1);
        else System.out.println(sb.toString());
*
* */