cf379d ac

#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>;

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, a22 = 0;
    ll b1 = 1, b2 = 2, b12 = 1, b21 = 1, b22 = 0;
    for (int i = 5; i <= k; ++i) {
        ll c1 = a1 + b1, c2 = a2 + b2;
        ll c12 = a12 + b12, c21 = a21 + b21 + ((i + 1) % 2);
        ll c22 = 0;
        switch (i) {
            case 3:
                c22 = 1;
                break;
            default:
                c22 = a22 + b22 + (i % 2);
                break;
        }
        a1 = b1, a2 = b2, a12 = b12, a21 = b21, a22 = b22;
        b1 = c1, b2 = c2, b12 = c12, b21 = c21, b22 = c22;
        dbg(i, b21);
    }
    if (k == 3) {
        b1 = a1, b2 = a2, b12 = a12, b21 = a21, b22 = a22;
    }
    if (k == 4) {
        // nothing
    }

    string s1, s2;
    for (int i = 0; i <= n / 2; ++i) {
        s2 = "";
        for (int j = 0; j <= m / 2; ++j) {
            if (x == i * b1 + j * b2) {
                dbg(i, b1, j, b2, i * b1 + j * b2, x);
                dbg(s1, s2);
                s1 += string(n - s1.size(), 'D');
                s2 += string(m - s2.size(), 'D');
                cout << s1 << '\n' << s2 << '\n';
                return 0;
            } else if (x == i * b1 + j * b2 + b12 && i * 2 + 1 <= n && j * 2 + 1 <= m) {
                dbg(i, b1, j, b2, b12, i * b1 + j * b2 + b12, x);
                s1 += string(n - 1 - s1.size(), 'D');
                s2 += string(m - 1 - s2.size(), 'D');
                s1 += 'A';
                s2 = 'C' + s2;
                cout << s1 << '\n' << s2 << '\n';
                return 0;
            } else if (x == i * b1 + j * b2 + b21 && i * 2 + 1 <= n && j * 2 + 1 <= m) {
                dbg(i, b1, j, b2, b21, i * b1 + j * b2 + b21, x);
                s1 += string(n - 1 - s1.size(), 'D');
                s2 += string(m - 1 - s2.size(), 'D');
                s1 = 'C' + s1;
                s2 += 'A';
                cout << s1 << '\n' << s2 << '\n';
                return 0;
            } else if (x == i * b1 + j * b2 + b12 + b21 + b22 && i * 2 + 2 <= n && j * 2 + 2 <= m) {
                dbg(i, b1, j, b2, b12, b21, b22, i * b1 + j * b2 + b12 + b21 + b22, x);
                s1 += string(n - 2 - s1.size(), 'D');
                s2 += string(m - 2 - s2.size(), 'D');
                s1 = 'C' + s1 + 'A';
                s2 = 'C' + s2 + 'A';
                cout << s1 << '\n' << s2 << '\n';
                return 0;
            } else if (x == i * b1 + j * b2 + b12 + b22 && i * 2 + 1 <= n && j * 2 + 2 <= m) {
                s1 += string(n - 1 - s1.size(), 'D');
                s2 += string(m - 2 - s2.size(), 'D');
                s1 += 'A';
                s2 = 'C' + s2 + 'A';
                cout << s1 << '\n' << s2 << '\n';
                return 0;
            } else if (x == i * b1 + j * b2 + b21 + b22 && i * 2 + 1 <= n && j * 2 + 2 <= m) {
                s1 += string(n - 1 - s1.size(), 'D');
                s2 += string(m - 2 - s2.size(), 'D');
                s1 = 'C' + s1;
                s2 = 'C' + s2 + 'A';
                cout << s1 << '\n' << s2 << '\n';
                return 0;
            } else if (x == i * b1 + j * b2 + b22 && j * 2 + 2 <= m) {
                s1 += string(n - s1.size(), 'D');
                s2 += string(m - 2 - s2.size(), 'D');
                s2 = 'C' + s2 + 'A';
                cout << s1 << '\n' << s2 << '\n';
                return 0;
            }
            s2 += "AC";
        }
        s1 += "AC";
    }
    cout << "Happy new year!" << endl;
    return 0;
};