OI XXXIII - ste (Alt)

// https://szkopul.edu.pl/problemset/problem/Vc3EYISNd8DRaR6CC1g_4Dhy/site/?key=statement

#include <bits/stdc++.h>

using namespace std;

const int K = 1000;
const int PAYLOAD_ROWS = 980;
const int PAYLOAD_COLS = 980;
const int MARKER_START_COL = 980;
const int ROW_IDX_START_COL = 990;
const int COL_IDX_START_ROW = 980;
const int FOOTER_START_ROW = 990;

void set_bit(vector<string>& M, int r, int c, int val) {
    M[r][c] = (val ? '1' : '0');
}

void run_encoder(int k) {
    int n;
    cin >> n;
    string s;
    cin >> s;

    if (k != K) {
        for (int i = 0; i < k; ++i) {
            for (int j = 0; j < k; ++j)
                cout << "0";
            cout << "\n";
        }
        return;
    }

    vector<string> M(K, string(K, '0'));
    vector<int> bits;

    for (int i = 0; i < 18; ++i) {
        bits.push_back((n >> i) & 1);
    }

    for (int i = 0; i < n; i += 4) {
        long long val = 0;
        long long power = 1;
        for (int j = 0; j < 4; ++j) {
            if (i + j < n) {
                val += (s[i + j] - 'a') * power;
            }
            power *= 26;
        }
        for (int b = 0; b < 19; ++b) {
            bits.push_back((val >> b) & 1);
        }
    }

    int bit_idx = 0;
    for (int r = 0; r < PAYLOAD_ROWS; ++r) {
        for (int c = 0; c < PAYLOAD_COLS; ++c) {
            if (bit_idx < bits.size()) {
                set_bit(M, r, c, bits[bit_idx++]);
            } else {
                set_bit(M, r, c, 0);
            }
        }
    }

    for (int c = 0; c < PAYLOAD_COLS; ++c) {
        for (int b = 0; b < 10; ++b) {
            set_bit(M, COL_IDX_START_ROW + b, c, (c >> b) & 1);
        }
    }

    for (int r = 0; r < FOOTER_START_ROW; ++r) {
        for (int b = 0; b < 10; ++b) {
            set_bit(M, r, ROW_IDX_START_COL + b, (r >> b) & 1);
        }
    }

    for (int r = 0; r < FOOTER_START_ROW; ++r) {
        for (int c = MARKER_START_COL; c < MARKER_START_COL + 10; ++c) {
            set_bit(M, r, c, 1);
        }
    }

    for (int i = 0; i < 10; ++i) {
        int r = FOOTER_START_ROW + i;
        int ones_count = i + 1;
        for (int j = 0; j < ones_count; ++j) {
            set_bit(M, r, K - 1 - j, 1);
        }
    }

    for (int i = 0; i < K; ++i) {
        cout << M[i] << "\n";
    }
}

void run_decoder(int k) {
    if (k != K) {
        vector<string> temp(k);
        for (int i = 0; i < k; ++i)
            cin >> temp[i];
        cout << "a\n";
        return;
    }

    vector<string> N(K);
    for (int i = 0; i < K; ++i)
        cin >> N[i];

    map<int, int> footer_rows_by_sum;
    vector<int> row_sums(K, 0);

    for (int r = 0; r < K; ++r) {
        int s = 0;
        for (char c : N[r])
            if (c == '1') s++;
        row_sums[r] = s;
        if (s >= 1 && s <= 10) {
            footer_rows_by_sum[s] = r;
        }
    }

    map<int, int> orig_col_to_curr;
    set<int> identified_cols;

    for (int s = 1; s <= 10; ++s) {
        int r = footer_rows_by_sum[s];
        for (int c = 0; c < K; ++c) {
            if (N[r][c] == '1' && identified_cols.find(c) == identified_cols.end()) {
                int orig_col = K - s;
                orig_col_to_curr[orig_col] = c;
                identified_cols.insert(c);
                break;
            }
        }
    }

    vector<string> sorted_rows(K);

    for (int r = 0; r < K; ++r) {
        if (row_sums[r] > 10) {
            int row_idx = 0;
            for (int b = 0; b < 10; ++b) {
                int curr_col = orig_col_to_curr[ROW_IDX_START_COL + b];
                if (N[r][curr_col] == '1') {
                    row_idx |= (1 << b);
                }
            }
            if (row_idx < FOOTER_START_ROW) {
                sorted_rows[row_idx] = N[r];
            }
        }
    }

    vector<int> payload_col_mapping(PAYLOAD_COLS);

    for (int c = 0; c < K; ++c) {
        if (identified_cols.count(c)) continue;

        int col_sum = 0;
        for (int r = 0; r < FOOTER_START_ROW; ++r) {
            if (sorted_rows[r][c] == '1') col_sum++;
        }

        if (col_sum == FOOTER_START_ROW) {
            continue;
        } else {
            int col_idx = 0;
            for (int b = 0; b < 10; ++b) {
                if (sorted_rows[COL_IDX_START_ROW + b][c] == '1') {
                    col_idx |= (1 << b);
                }
            }
            if (col_idx < PAYLOAD_COLS) {
                payload_col_mapping[col_idx] = c;
            }
        }
    }

    vector<int> bits;
    bits.reserve(PAYLOAD_ROWS * PAYLOAD_COLS);

    for (int r = 0; r < PAYLOAD_ROWS; ++r) {
        for (int c_orig = 0; c_orig < PAYLOAD_COLS; ++c_orig) {
            int c_curr = payload_col_mapping[c_orig];
            bits.push_back(sorted_rows[r][c_curr] == '1' ? 1 : 0);
        }
    }

    int ptr = 0;

    int n = 0;
    for (int i = 0; i < 18; ++i) {
        if (bits[ptr++]) n |= (1 << i);
    }

    string s = "";
    int chars_read = 0;

    while (chars_read < n) {
        long long val = 0;
        for (int i = 0; i < 19; ++i) {
            if (bits[ptr++]) val |= (1LL << i);
        }

        for (int j = 0; j < 4; ++j) {
            if (chars_read < n) {
                char c = 'a' + (val % 26);
                val /= 26;
                s += c;
                chars_read++;
            }
        }
    }

    cout << s << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int k;
    cin >> k;
    string type;
    cin >> type;

    if (type == "encoder") {
        run_encoder(k);
    } else {
        run_decoder(k);
    }

    return 0;
}