vector<bitset<4>> HexToBinary (string x) {
    vector<bitset<4>> result;
    for (int i=0; i < x.size(); i++) {
        int k;
        if (x[i] <= 57) {
            k = x[i] - 48;
        } else {
            k = x[i] - 55;
        }
        bitset<4> temp(k);
        result.push_back(temp);
    }
    return result;
}

string BinaryToHex (vector<bitset<4>> x) {
    string result;
    for (int i=0; i < x.size(); i++) {
        int k = x[i].to_ulong();
        if (k < 10) {
            result.push_back(static_cast<char>(k+48));
        } else {
            result.push_back(static_cast<char>(k+55));
        }
    }
    int index = 0;
    while (index < result.size()-1) {
        if (result[index] != '0') {
            break;
        }
        index++;
    }
    result.erase(result.begin(), result.begin()+index);
    return result;
}

void aOrB(int k, string a, string b, string c) {
    vector<bitset<4>> binaryA = HexToBinary(a);
    vector<bitset<4>> binaryB = HexToBinary(b);
    vector<bitset<4>> binaryC = HexToBinary(c);
    int changesRemaining = k;
    
    //make necessary changes to A and B
    int d1 = binaryA.size() - binaryC.size();
    int d2 = binaryB.size() - binaryC.size();
    for (int i=0; i < d1; i++) {
        changesRemaining = changesRemaining - binaryA[i].count();
    }
    for (int i=0; i < d2; i++) {
        changesRemaining = changesRemaining - binaryB[i].count();
    }
    binaryA.erase(binaryA.begin(), binaryA.begin()+d1);
    binaryB.erase(binaryB.begin(), binaryB.begin()+d2);
    d1 = binaryA.size() - binaryC.size();
    d2 = binaryB.size() - binaryC.size();
    binaryA.insert(binaryA.begin(), abs(d1), bitset<4>());
    binaryB.insert(binaryB.begin(), abs(d2), bitset<4>());
    for (int i=0; i < binaryC.size(); i++) {
        for (int j=3; j >= 0; j--) {
            if (binaryC[i][j] == 0) {
                changesRemaining = changesRemaining - binaryA[i][j] - binaryB[i][j];
                binaryA[i][j] = 0;
                binaryB[i][j] = 0;
            }
            if (binaryC[i][j] == 1 and (binaryA[i][j] | binaryB[i][j]) == 0) {
                binaryB[i][j] = 1;
                changesRemaining--;
            }
        }
    }
    if (changesRemaining < 0) {
        cout << -1 << "\n";
        return;
    }
    
    //optimize A and B, try to make A the smallest possible
    for (int i=0; i < binaryC.size(); i++) {
        for (int j=3; j >= 0; j--) {
            if (changesRemaining == 0) {
                cout << BinaryToHex(binaryA) << "\n" << BinaryToHex(binaryB) << "\n" ;
                return;
            }
            if (binaryC[i][j] == 1) {
                if ((binaryA[i][j]&binaryB[i][j]) == 1) {
                    binaryA[i][j] = 0;
                    changesRemaining--;
                } else if (binaryA[i][j] == 1 and binaryB[i][j] == 0 and changesRemaining >= 2) {
                    binaryA[i][j] = 0;
                    binaryB[i][j] = 1;
                    changesRemaining = changesRemaining - 2;
                }
            }
        }
    }
    cout << BinaryToHex(binaryA) << "\n" << BinaryToHex(binaryB) << "\n" ;
}