cf379d wa

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&... values)
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << endl;
}

template <class T> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m)); }
template <class T> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n)); }
template <class T, T init> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m, init)); }
template <class T, T init> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n, init)); }

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using vl = vector<ll>;
using vi = vector<int>;

ll extgcd(ll a, ll b, ll &m, ll &n)
{
    if (a == 0) {
        m = 0, n = 1;
        return b;
    }
    ll ret = extgcd(b % a, a, m, n);
    ll tmp = m;
    m = n - (b / a) * m;
    n = tmp;
    return ret;
}

string multiple(ll x)
{
    dbg(x);
    string ret = "";
    string cur = "AC";
    while (x) {
        if (x & 1)
            ret = ret + cur;
        cur = cur + cur;
        x /= 2;
    }
    return ret;
}

int main(int argc, char **argv)
{
    int k, x, n, m;
    cin >> k >> x >> n >> m;
    ll a1 = 1, a2 = 1, a12 = 1, a21 = 0;
    ll b1 = 1, b2 = 2, b12 = 1, b21 = 1;
    for (int i = 3; i <= k; ++i) {
        ll c1 = a1 + b1, c2 = a2 + b2;
        ll c12 = a12 + b12, c21 = a21 + b21 + (i + 1 % 2);
        a1 = b1, a2 = b2, a12 = b12, a21 = b21;
        b1 = c1, b2 = c2, b12 = c12, b21 = c21;
    }

    ll f1, f2;
    ll g12 = extgcd(b1, b2, f1, f2);
    assert(b1 * f1 + b2 * f2 == g12);
    assert(g12 > 0);
    if (x % g12 == 0) {
        ll k = x / g12;
        assert(k > 0);
        ll lb1 = -f1 / b2, lb2 = (f2 - m / 2 / k) / b1;
        ll ub1 = (n / 2 / k - f1) / b2, ub2 = f2 / b1;
        if (max(lb1, lb2) <= min(ub1, ub2)) {
            ll k1 = max(lb1, lb2);
            // ll k1 = min(ub1, ub2);
            string s1 = multiple((f1 + k1 * b2) * k);
            string s2 = multiple((f2 - k1 * b1) * k);
            s1 += string(n - s1.size(), 'D');
            s2 += string(m - s2.size(), 'D');
            cout << s1 << '\n' << s2 << '\n';
            return 0;
        }
    }
    if ((x - b12) % g12 == 0) {
        ll k = (x - b12) / g12;
        n -= 1;
        m -= 1;
        ll lb1 = -f1 / b2, lb2 = (f2 - m / 2 / k) / b1;
        ll ub1 = (n / 2 / k - f1) / b2, ub2 = f2 / b1;
        if (max(lb1, lb2) <= min(ub1, ub2)) {
            ll k1 = max(lb1, lb2);
            string s1 = multiple((f1 + k1 * b2) * k);
            string s2 = multiple((f2 - k1 * b1) * k);
            s1 += string(n - s1.size(), 'D');
            s2 += string(m - s2.size(), 'D');
            s1 += 'A';
            s2 = "C" + s2;
            cout << s1 << '\n' << s2 << '\n';
            return 0;
        }
    }
    if ((x - b21) % g12 == 0) {
        ll k = (x - b12) / g12;
        n -= 1;
        m -= 1;
        ll lb1 = -f1 / b2, lb2 = (f2 - m / 2 / k) / b1;
        ll ub1 = (n / 2 / k - f1) / b2, ub2 = f2 / b1;
        if (max(lb1, lb2) <= min(ub1, ub2)) {
            ll k1 = max(lb1, lb2);
            string s1 = multiple((f1 + k1 * b2) * k);
            string s2 = multiple((f2 - k1 * b1) * k);
            s1 += string(n - s1.size(), 'D');
            s2 += string(m - s2.size(), 'D');
            s2 += 'A';
            s1 = "C" + s2;
            cout << s1 << '\n' << s2 << '\n';
            return 0;
        }
    }
    if ((x - b12 - b21) % g12 == 0) {
        ll k = (x - b12) / g12;
        n -= 2;
        m -= 2;
        ll lb1 = -f1 / b2, lb2 = (f2 - m / 2 / k) / b1;
        ll ub1 = (n / 2 / k - f1) / b2, ub2 = f2 / b1;
        if (max(lb1, lb2) <= min(ub1, ub2)) {
            ll k1 = max(lb1, lb2);
            string s1 = multiple((f1 + k1 * b2) * k);
            string s2 = multiple((f2 - k1 * b1) * k);
            s1 += string(n - s1.size(), 'D');
            s2 += string(m - s2.size(), 'D');
            s1 = "C" + s1 + "A";
            s2 = "C" + s2 + "A";
            cout << s1 << '\n' << s2 << '\n';
            return 0;
        }
    }
    cout << "Happy new year!" << endl;
    return 0;
};