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

public class Main {
    static char different(char a, char b) {
        int l1 = a - 'a';
        int l2 = b - 'a';
        if (l1 != l2) {
            if (l1 != 0 && l2 != 0) {
                return (char) ((l1 + l2) % 26 + 'a');
            } else if (l1 != 25 && l2 != 25) {
                return (char)  ((l1 + l2 + 1) % 26 + 'a');
            } else {
                return (char) ((l1 + l2 + 2) % 26 + 'a');
            }
        } else {
            return (char) ((l1 + 1) % 26 + 'a');
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), t = scanner.nextInt();
        String s1 = scanner.next(), s2 = scanner.next();
        int differs = 0;
        for (int i = 0; i < n; i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                differs++;
            }
        }
        if (differs > t) {
            if (differs > 2 * t) {
                System.out.println(-1);
                return;
            }
            int a = 0, b = 0, c = 0, tt = t;
            while (differs - b > tt) {
                b += 2;
                tt--;
            }
            if (tt > 0) {
                c = differs - b;
                if (c > tt) {
                    System.out.println(-1);
                    return;
                }
                tt -= c;
                if (tt > 0) {
                    if (n - differs < tt) {
                        System.out.println(-1);
                        return;
                    }
                    a = tt;
                }
            }
            for (int i = 0, aa = 0, bb = 0, cc = 0; i < n; i++) {
                char c1 = s1.charAt(i), c2 = s2.charAt(i);
                if (c1 == c2) {
                    if (aa < a) {
                        System.out.print(different(c1, c2));
                        aa++;
                    } else {
                        System.out.print(c1);
                    }
                } else {
                    if (bb < b) {
                        if (bb % 2 == 0) {
                            System.out.print(c1);
                        } else {
                            System.out.print(c2);
                        }
                        bb++;
                    } else if (cc < c) {
                        System.out.print(different(c1, c2));
                    }
                }
            }
            return;
        }
        int neededDifsEqs = t - differs;
        for (int i = 0, difs = 0, difsEqs = 0; i < n; i++) {
            int l1 = s1.charAt(i) - 'a';
            int l2 = s2.charAt(i) - 'a';
            if (l1 != l2 && difs < t) {
                if (l1 != 0 && l2 != 0) {
                    System.out.print((char) ((l1 + l2) % 26 + 'a'));
                } else if (l1 != 25 && l2 != 25) {
                    System.out.print((char) ((l1 + l2 + 1) % 26 + 'a'));
                } else {
                    System.out.print((char) ((l1 + l2 + 2) % 26 + 'a'));
                }
                difs++;
            } else if (difsEqs < neededDifsEqs) {
                System.out.print((char) ((l1 + 1) % 26 + 'a'));
                difsEqs++;
            } else {
                System.out.print(s1.charAt(i));
            }
        }
    }
}