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.io.*;

public class TaskC {
    private FastScanner in;
    private PrintWriter out;

    public void solve() throws IOException {
        int n = in.nextInt(), ok = n - in.nextInt();
        String a = in.next(), b = in.next();
        List<Integer> same = new ArrayList<>(), diff = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (a.charAt(i) != b.charAt(i)) {
                diff.add(i);
            } else {
                same.add(i);
            }
        }
        char[] result = new char[n];
        for (int i : same) {
            result[i] = a.charAt(i);
        }
        for (int i : diff) {
            result[i] = diff(a.charAt(i), b.charAt(i));
        }

        if (ok <= same.size()) {
            for (int i = 0; i < same.size() - ok; i++) {
                result[same.get(i)] = diff(a.charAt(same.get(i)));
            }
        } else {
            int rem = ok - same.size();
            if (diff.size() / 2 < rem) {
                out.println("-1");
                return;
            } else {
                for (int i = 0; i < rem * 2; i++) {
                    result[diff.get(i)] = i % 2 == 0 ? a.charAt(diff.get(i)) : b.charAt(diff.get(i));
                }
            }
        }
        out.println(new String(result));
    }

    public char diff(char c) {
        return c == 'a' ? 'b' : 'a';
    }

    public char diff(char c1, char c2) {
        if (c1 != 'a' && c2 != 'a') {
            return 'a';
        }
        if (c1 != 'b' && c2 != 'b') {
            return 'b';
        }
        return 'c';
    }

    public void run() {
        try {
            in = new FastScanner();
            out = new PrintWriter(System.out);
            solve();
            out.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private class FastScanner {
        private BufferedReader br;
        private StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

    }

    public static void main(String[] arg) {
        new TaskC().run();
    }
}