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 s_1, s_2 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 s_3 of length n, such that f(s_1, s_3) = f(s_2, s_3) = t. If there is no such string, print  - 1.


-----Input-----

The first line contains two integers n and t (1 ≤ n ≤ 10^5, 0 ≤ t ≤ n).

The second line contains string s_1 of length n, consisting of lowercase English letters.

The third line contain string s_2 of length n, consisting of lowercase English letters.


-----Output-----

Print a string of length n, differing from string s_1 and from s_2 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

Difficulty: interview

Starter code:

Solutions:
def main():
    import sys
    
    n, t, s1, s2 = sys.stdin.read().split()
    n, t = int(n), int(t)
    
    result = [-1] * n
    rest = n - t
    for i in range(n):
        if rest == 0: break
        if s1[i] == s2[i]:
            result[i] = s1[i]
            rest -= 1
    k = rest
    for i in range(n):
        if k == 0: break
        if result[i] == -1:
            result[i] = s1[i]
            k -= 1
    k = rest
    for i in range(n):
        if k == 0: break
        if result[i] == -1:
            result[i] = s2[i]
            k -= 1    
    if k > 0:
        print(-1)
        return
    for i in range(n):
        if result[i] == -1:
            for j in range(ord('a'), ord('a') + 4):
                if chr(j) != s1[i] and chr(j) != s2[i]:
                    result[i] = chr(j)
                    break
    
    sys.stdout.write(''.join(result))
    
main()

#In the name of Allah

from sys import stdin, stdout
input = stdin.readline

n, t = list(map(int, input().split()))
s1 = input()[:-1]
s2 = list(input()[:-1])
if t > n:
        stdout.write("-1")
        return

d = [False] * n
m = 0
for i in range(n):
       if s2[i] == s1[i]:
               d[i] = True
               m += 1
d1 = d2 = n - t
ans = [""] * n

for i in range(n):
        if d[i] and d2 != 0 and d1 != 0:
                d2 -= 1
                d1 -= 1
                ans[i] = s1[i]
                #t -= 1

for i in range(n):
        if not d[i]:
                if d1 != 0:
                        ans[i] = s1[i]
                        d1 -= 1
                        continue
                if d2 != 0:
                        ans[i] = s2[i]
                        d2 -= 1
                        continue

for j in range(n):
        if ans[j] == "":
                for i in range(26):
                        al = chr(ord("a") + i)
                        if s1[j] != al and s2[j] != al:
                                ans[j] = al
                                break
                if ans[j] == "":
                        stdout.write("-1")

                
if d1 == 0 and d2 == 0:
        stdout.write("".join(ans))
else:
        stdout.write("-1")


n, m = map(int, input().split())
a = input()
b = input()
c = []
d = [0] * n
c = [i for i in range(n) if a[i] == b[i]]
l = len(c)
for i in range(min(l, n-m)):
    d[c[i]] = a[c[i]]
if l < n-m:
    u = n-m-l
    if l + u + u > n:
        print(-1)
        return
    else:
        u = n-m-l
        for i in range(n):
            if d[i] == 0 and u > 0:
                d[i] = a[i]
                u -= 1
                if u == 0: break
        u = n-m-l
        for i in range(n):
            if d[i] == 0 and u > 0:
                d[i] = b[i]
                u -= 1
                if u == 0: break
for i in range(n):
    if d[i] == 0:
        for e in ['a','b','c']:
            if e != a[i] and e != b[i]:
                print(e, end='')
                break
    else:
        print(d[i], end='')


import sys

n, t = map(int, input().split())

s1 = input()
s2 = input()

same = sum([1 for i in range(n) if s1[i] ==s2[i]])

def other(c1, c2):
    ans = 'a'
    while ans == c1 or ans == c2:
        ans = chr(ord(ans) + 1)
    return ans

if same + 2 * t < n:
    print(-1)
    return

samehave = 0
sames1 = 0
sames2 = 0

ans = ['v'] * n

for i in range(n):
    if s1[i] == s2[i]:
        if sames1 < n - t and sames2 < n - t:
            ans[i] = s1[i]
            sames1 += 1
            sames2 += 1
        else:
            ans[i] = other(s1[i], s2[i])

for i in range(n):
    if s1[i] != s2[i]:
        if sames1 < n - t:
            sames1 += 1
            ans[i] = s1[i]
        elif sames2 < n - t:
            sames2 += 1
            ans[i] = s2[i]
        else:
            ans[i] = other(s1[i], s2[i])
        

print(*ans, sep='')

def f(sa, sb):
    ans = 0
    for i in range(len(sa)):
        ans += sa[i] != sb[i]
    return ans

def third(a0, b0):
    if a0 != "a" and b0 != "a":
        return "a"
    if a0 != "b" and b0 != "b":
        return "b"
    if a0 != "c" and b0 != "c":
        return "c"
n, t = list(map(int, input().split()))
s1 = input()
s2 = input()
sovp = n - f(s1, s2) #совпадающих из нашей строки
needsovp = n - t #необходимо совпадающих
ans = [0] * n
need1r = needsovp - sovp
need2r = needsovp - sovp
if sovp >= needsovp:
    for i in range(n):
        if s1[i] != s2[i]:
            ans[i] = third(s1[i], s2[i])
        elif needsovp > 0:
            ans[i] = s1[i]
            needsovp -= 1
        else:
            ans[i] = third(s1[i], s2[i])
    if not(f("".join(ans), s1) == f("".join(ans), s2) == t):
        print(-1)
    else:
        print(*ans, sep="")
else:
    for i in range(n):
        if s1[i] != s2[i]:
            if need1r > 0:
                need1r -= 1
                ans[i] = s1[i]
            elif need2r > 0:
                need2r -= 1
                ans[i] = s2[i]
            else:
                ans[i] = third(s1[i], s2[i])
        else:
            ans[i] = s1[i]
    if not(f("".join(ans), s1) == f("".join(ans), s2) == t):
        print(-1)
    else:
        print(*ans, sep="")


import sys


#sys.stdin = open("input.txt")
#sys.stdout = open("output.txt", "w")

n, t = [int(i) for i in input().split()]
s1 = input()
s2 = input()

common = 0
diff = 0
for i in range(n):
	if s1[i] == s2[i]:
		common += 1
	else:
		diff += 1

chars = 'abc'
ans = []
if common >= n - t:
	unc_common = n - t 
	for i in range(n):
		if s1[i] == s2[i] and unc_common > 0:
			ans.append(s1[i])
			unc_common -= 1
		else:
			for char in chars:
				if char != s1[i] and char != s2[i]:
					ans.append(char)
					break
	print(''.join(ans))
else:
	unch = n - t - common
	unch1 = 0
	unch2 = 0
	if 2 * unch <= diff:
		for i in range(n):
			if s1[i] == s2[i]:
				ans.append(s1[i])
			else:
				if unch1 < unch:
					ans.append(s1[i])
					unch1 += 1
				elif unch2 < unch:
					ans.append(s2[i])
					unch2 += 1
				else:
					for char in chars:
						if char != s1[i] and char != s2[i]:
							ans.append(char)
							break
		print(''.join(ans))	
	else:
		print(-1)


def f(s1, s2):
    return sum(0 if ch1 == ch2 else 1 for ch1, ch2 in zip(s1, s2))


def choose_different(ch1, ch2):
    if ch1 != 'a' and ch2 != 'a':
        return 'a'
    if ch1 != 'b' and ch2 != 'b':
        return 'b'
    return 'c'


def calc_s3(s1, s2, in_match, out_match):
    l3 = []
    in_match_taken = 0
    out_match_taken_1 = 0
    out_match_taken_2 = 0
    for ch1, ch2 in zip(s1, s2):
        if ch1 == ch2:
            if in_match_taken < in_match:
                ch3 = ch1
                in_match_taken += 1
            else:
                ch3 = choose_different(ch1, ch2)
        else:
            if out_match_taken_1 < out_match:
                ch3 = ch1
                out_match_taken_1 += 1
            elif out_match_taken_2 < out_match:
                ch3 = ch2
                out_match_taken_2 += 1
            else:
                ch3 = choose_different(ch1, ch2)

        l3.append(ch3)

    return ''.join(l3)


def main():
    n, t = [int(t) for t in input().split()]
    s1 = input()
    s2 = input()

    dif_12 = f(s1, s2)
    match_12 = n - dif_12
    highest_match = match_12 + dif_12 // 2

    match_require = n - t

    if match_require > highest_match:
        print(-1)
        return
    if match_12 >= match_require:
        in_match = match_require
        out_match = 0
    else:
        in_match = match_12
        out_match = match_require - match_12

    s3 = calc_s3(s1, s2, in_match, out_match)
    print(s3)


def __starting_point():
    main()

__starting_point()