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 PYTHON3):

Solution:
def read_numbers():
    return list(map(int, input().split()))

def get_other_char(a, b):
    for c in 'abc':
        if c != a and c != b:
            return c

n, t = read_numbers()
word1 = input()
word2 = input()

# find a word, that has minimal distance to both of them
# first, number of differences
diffs = len([idx for idx, (c1, c2) in enumerate(zip(word1, word2)) if c1 != c2])
#not_diffs = [idx for idx, (c1, c2) in enumerate(zip(word1, word2)) if c1 == c2]

minimum = (diffs + 1) // 2

switches = diffs - t if t <= diffs else 0
switch_polarity = 0

if t < minimum:
    print(-1)
else:
    # create new word
    new_word = []
    for c1, c2 in zip(word1, word2):
        if c1 == c2:
            if t > diffs:
                new_word.append(get_other_char(c1, c2))
                t -= 1
            else:
                new_word.append(c1)
        else:
            if switches:
                if switch_polarity == 0:
                    new_word.append(c1)
                    switch_polarity = 1
                else:
                    new_word.append(c2)
                    switch_polarity = 0
                    switches -= 1
            else:
                new_word.append(get_other_char(c1, c2))

    print(''.join(new_word))