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

Solution:
#include <bits/stdc++.h>
using namespace std;
string s1, s2, s3;
string::iterator it1, it2;
vector<int> ind;
int n, t, dff, cnt, cnt2, cnt3;
char res[100010], ch;
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> t;
  cin >> s1 >> s2;
  int i = 1;
  dff = 0;
  for (it1 = s1.begin(), it2 = s2.begin(); it1 != s1.end(); it1++, it2++) {
    if ((*it1) != (*it2)) dff++;
    i++;
  }
  if (dff <= t) {
    cnt = t - dff;
    i = 1;
    for (it1 = s1.begin(), it2 = s2.begin(); it1 != s1.end(); it1++, it2++) {
      if ((*it1) == (*it2)) {
        res[i] = (*it1);
        if (cnt > 0) {
          if (res[i] == 'a')
            res[i] = 'b';
          else
            res[i] = 'a';
          cnt--;
        }
      } else {
        for (int j = 0; j < 3; j++) {
          ch = (char)('a' + j);
          if (ch != (*it1) && ch != (*it2)) {
            res[i] = ch;
            break;
          }
        }
      }
      i++;
    }
  } else if (dff <= (2 * t)) {
    cnt = (2 * t) - dff;
    cnt2 = t - cnt;
    cnt3 = cnt2;
    i = 1;
    for (it1 = s1.begin(), it2 = s2.begin(); it1 != s1.end(); it1++, it2++) {
      if ((*it1) == (*it2)) {
        res[i] = (*it1);
      } else {
        if (cnt > 0) {
          cnt--;
          for (int j = 0; j < 3; j++) {
            ch = (char)('a' + j);
            if (ch != (*it1) && ch != (*it2)) {
              res[i] = ch;
              break;
            }
          }
        } else if (cnt2 > 0) {
          cnt2--;
          res[i] = (*it1);
        } else if (cnt3 > 0) {
          cnt3--;
          res[i] = (*it2);
        }
      }
      i++;
    }
  } else {
    cout << "-1\n";
    return 0;
  }
  for (i = 1; i <= n; i++) {
    s3.push_back(res[i]);
  }
  cout << s3 << "\n";
  return 0;
}