using namespace std;
int n, t;
string s1, s2;
int count_matching_indexes(void)
{
    int ans = 0;
    for (int i = 0; i < n; ++i)
        if (s1[i] == s2[i])
            ++ans;
    return ans;
}
char anything_but(char c, char d)
{
    for (char x = 'a'; x <= 'z'; ++x)
        if (x != c and x != d)
            return x;
    return 0;
}
string solve(void)
{
    string ans(n, ' ');
    int pt = n - t;
    int match_ix = count_matching_indexes();
    int rm_1 = max(0, pt - match_ix);
    int rm_2 = rm_1;
    int pmatch = min(match_ix, pt);
    for (int i = 0; i < n; ++i)
    {
        if (s1[i] != s2[i])
        {
            if (rm_1 > 0)
            {
                ans[i] = s1[i];
                --rm_1;
            }
            else if (rm_2 > 0)
            {
                ans[i] = s2[i];
                --rm_2;
            }
            else
                ans[i] = anything_but(s1[i], s2[i]);
        }
        else
        {
            if (pmatch > 0)
            {
                ans[i] = s1[i];
                --pmatch;
            }
            else
                ans[i] = anything_but(s1[i], s2[i]);
        }
    }
    if (rm_1 > 0 or rm_2 > 0)
        return "-1";
    else
        return ans;
}
int main(void)
{
    cin >> n >> t >> s1 >> s2;
    cout << solve() << endl;
    return 0;
}

using namespace std;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int main(void)
{
    int n, gi;
    multiset<int, greater<int>> ms;
    vector<int> a;
    cin >> n;
    for (int i = 0; i < n * n; ++i)
    {
        cin >> gi;
        ms.insert(gi);
    }
    while ((int)a.size() < n)
    {
        a.push_back(*ms.begin());
        ms.erase(ms.begin());
        for (int i = 0, nc = a.size() - 1; i < nc; ++i)
        {
            for (int j = 0; j < 2; ++j)
            {
                auto it = ms.find(gcd(a[i], a[nc]));
                ms.erase(it);
            }
        }
    }
    for (auto ai : a)
        cout << ai << " ";
    cout << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 2e5 + 11;
int n, a[NMAX];
double f(double x)
{
    double mn = 0, mx = 0, sm = 0;
    for (int i = 0; i < n; i++)
    {
        sm += a[i] - x;
        mn = min(mn, sm);
        mx = max(mx, sm);
    }
    return abs(mx - mn);
};
double ternary_search(double l, double r, function<double(double)> f)
{
    double eps = 5e-12;
    while (r - l > eps)
    {
        double m1 = l + (r - l) / 3.0;
        double m2 = r - (r - l) / 3.0;
        if (f(m1) > f(m2))
            l = m1;
        else
            r = m2;
    }
    return f(l);
}
int main(void)
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    cout << setprecision(15) << fixed << ternary_search(-1e4, 1e4, f) << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
const int NMAX = 12 + 8;
int t, n;
int x[NMAX];
void print_ans(vi ans)
{
    for (auto &elem : ans)
    {
        if (&elem != &ans.front())
            cout << "+";
        cout << elem;
    }
    cout << endl;
}
bool backtrack(int pos, int sum, vi cur_ans)
{
    bool found = false;
    if (sum == t)
    {
        print_ans(cur_ans);
        return true;
    }
    if (sum > t or pos > n)
        return false;
    for (int i = pos; i < n; ++i)
    {
        if (i != pos and
            x[i] == x[i - 1])
            continue;
        cur_ans.push_back(x[i]);
        found |= backtrack(i + 1, sum + x[i], cur_ans);
        cur_ans.pop_back();
    }
    return found;
}
int main(void)
{
    while (cin >> t >> n and n != 0)
    {
        for (int i = 0; i < n; ++i)
            cin >> x[i];
        cout << "Sums of " << t << ":" << endl;
        if (not backtrack(0, 0, vi()))
            cout << "NONE" << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
struct edge
{
    int a, b, c;
};
const int INF = 1e9;
int n, m;
vector<edge> edges;
bool solve(void)
{
    vi d(n, INF);
    d[0] = 0;
    bool negcycle;
    for (int i = 0; i < n; ++i)
    {
        negcycle = false;
        for (const auto &e : edges)
        {
            if (d[e.a] < INF and d[e.b] > d[e.a] + e.c)
            {
                d[e.b] = max(-INF, d[e.a] + e.c);
                negcycle = true;
            }
        }
    }
    return negcycle;
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        edges.assign(m, {});
        for (auto &e : edges)
            cin >> e.a >> e.b >> e.c;
        cout << (solve() ? "possible" : "not possible") << endl;
    }
    return 0;
}

using namespace std;
map<string, string> mem;
bool is_divisible_eight(string n)
{
    int len = n.size();
    if ((n[len - 1] - '0') % 2 == 1)
        return false;
    else if (len <= 3)
        return (stoi(n) % 8) == 0;
    else
        return is_divisible_eight(n.substr(len - 3, 3));
}
string dp(string n)
{
    int len = n.size();
    string copy;
    if (len == 0)
        return "x";
    if (len == 1 and (n[0] != '8' and n[0] != '0'))
        return "x";
    if (len > 1 and n[0] == '0')
        return "x";
    if (is_divisible_eight(n))
        return n;
    string &ans = mem[n];
    if (ans != "")
        return ans;
    for (int i = max(0, len - 3); i < len; ++i)
    {
        copy = n;
        ans = dp(copy.erase(i, 1));
        if (ans != "x")
            return ans;
    }
    return ans;
}
int main(void)
{
    string n;
    cin >> n;
    while ((n[n.size() - 1] - '0') % 2 == 1)
        n.pop_back();
    string ans = dp(n);
    if (ans == "x")
        cout << "NO";
    else
        cout << "YES" << endl << ans;
    cout << endl;
    return 0;
}

using namespace std;
using ll = long long;
const int NMAX = 2e5 + 11;
const int INF = 1e18 + 11;
ll n, a[NMAX], seg[4 * NMAX], lazy[4 * NMAX];
void build(ll a[], ll v, ll tl, ll tr)
{
    if (tl == tr)
        seg[v] = a[tl];
    else
    {
        ll tm = (tl + tr) / 2;
        build(a, 2 * v, tl, tm);
        build(a, 2 * v + 1, tm + 1, tr);
        seg[v] = min(seg[2 * v], seg[2 * v + 1]);
    }
}
void lazy_propagate(ll v, ll tl, ll tr, ll val)
{
    seg[v] += val;
    if (tl != tr)
    {
        lazy[2 * v] += val;
        lazy[2 * v + 1] += val;
    }
    lazy[v] = 0;
}
void update(ll v, ll tl, ll tr, ll ql, ll qr, ll delta)
{
    if (lazy[v] != 0)
        lazy_propagate(v, tl, tr, lazy[v]);
    if (ql > qr)
        return;
    else if (tl == ql and tr == qr)
        lazy_propagate(v, tl, tr, delta);
    else
    {
        ll tm = (tl + tr) / 2;
        update(2 * v, tl, tm, ql, min(tm, qr), delta);
        update(2 * v + 1, tm + 1, tr, max(tm + 1, ql), qr, delta);
        seg[v] = min(seg[2 * v], seg[2 * v + 1]);
    }
}
ll query(ll v, ll tl, ll tr, ll ql, ll qr)
{
    if (lazy[v] != 0)
        lazy_propagate(v, tl, tr, lazy[v]);
    if (ql > qr)
        return INF;
    else if (tl == ql and tr == qr)
        return seg[v];
    else
    {
        ll tm = (tl + tr) / 2;
        return min(query(2 * v, tl, tm, ql, min(tm, qr)),
                   query(2 * v + 1, tm + 1, tr, max(tm + 1, ql), qr));
    }
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll q, l, r, delta;
    cin >> n;
    for (ll i = 0; i < n; ++i)
        cin >> a[i];
    build(a, 1, 0, n - 1);
    cin >> q;
    while (q--)
    {
        cin >> l >> r;
        if (cin.peek() != '\n')
        {
            cin >> delta;
            if (l > r)
            {
                update(1, 0, n - 1, l, n - 1, delta);
                update(1, 0, n - 1, 0, r, delta);
            }
            else
                update(1, 0, n - 1, l, r, delta);
        }
        else
        {
            if (l > r)
                cout << min(query(1, 0, n - 1, l, n - 1),
                            query(1, 0, n - 1, 0, r))
                     << endl;
            else
                cout << query(1, 0, n - 1, l, r) << endl;
        }
    }
    return 0;
}

using namespace std;
using ll = long long;
const int CMAX = 26;
map<ll, ll> m[CMAX + 1];
int x[CMAX + 1];
ll solve(string s)
{
    int n = s.size(), cur;
    ll ans = 0, sum = 0;
    for (int i = 0; i < n; ++i)
    {
        cur = s[i] - 'a';
        ans += m[cur][sum];
        sum += x[cur];
        ++m[cur][sum];
    }
    return ans;
}
int main(void)
{
    string s;
    for (int i = 0; i < CMAX; ++i)
        cin >> x[i];
    cin >> s;
    cout << solve(s) << endl;
    return 0;
}

using namespace std;
using ll = long long;
using vi = vector<int>;
int main(void)
{
    int n;
    while (cin >> n and n != 0)
    {
        int pi;
        while (cin >> pi and pi != 0)
        {
            try
            {
                vector<bool> visited(n + 1, false);
                stack<int> s;
                for (int i = 0; i < n; ++i)
                {
                    if (i > 0)
                        cin >> pi;
                    if (not visited[pi])
                    {
                        for (int x = 1; x <= pi; ++x)
                        {
                            if (not visited[x])
                            {
                                s.push(x);
                                visited[x] = true;
                            }
                        }
                    }
                    else
                    {
                        if ((int)s.size() == 0 or s.top() != pi)
                        {
                            for (; i < n - 1; ++i)
                                cin >> pi;
                            throw -1;
                        }
                    }
                    s.pop();
                }
                cout << "Yes" << endl;
            }
            catch (int e)
            {
                cout << "No" << endl;
            }
        }
        cout << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
int const NMAX = 100 + 11;
int n, vis_status[NMAX];
string s[NMAX];
vi g[NMAX], order;
bool toposort(int u)
{
    if (vis_status[u] == 1)
        return false;
    if (vis_status[u] == 2)
        return true;
    vis_status[u] = 1;
    for (int v : g[u])
        if (not toposort(v))
            return false;
    vis_status[u] = 2;
    order.push_back(u);
    return true;
}
bool compare(int i, int j)
{
    int ix = 0, ni = s[i].size(), nj = s[j].size();
    while (ix < ni and ix < nj and s[i][ix] == s[j][ix])
        ++ix;
    if (ix != ni and ix == nj)
        return false;
    else if (ix != ni and ix != nj)
        g[s[i][ix] - 'a'].push_back(s[j][ix] - 'a');
    return true;
}
bool sorteable(void)
{
    for (int i = 0; i < n - 1; ++i)
        for (int j = i + 1; j < n; ++j)
            if (not compare(i, j))
                return false;
    for (int u = 0; u < 26; ++u)
        if (not vis_status[u] and not toposort(u))
            return false;
    return true;
}
int main(void)
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> s[i];
    if (sorteable())
        for_each(order.rbegin(),
                 order.rend(),
                 [](int cix) { cout << (char)(cix + 'a'); }),
            cout << endl;
    else
        cout << "Impossible" << endl;
    return 0;
}