margi

#include <bits/stdc++.h>

using namespace std;

ifstream fin("margi.in");
ofstream fout("margi.out");

vector < string > a;
vector < vector < int > > dp;
vector < int > A, B;

int calc_sum(int x1, int y1, int x2, int y2) {
    return dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
}

int solveA(int x, int y, int dim, vector < int > &rez) {
    if(dim == 1)
        return 0;
    int new_dim = dim >> 1;
    vector < int > v(5, -1);
    vector < vector < int > > cand(5);
    v[1] = solveA(x, y, new_dim, cand[1]);
    v[1] += calc_sum(x, y, x + new_dim - 1, y + new_dim - 1);
    v[2] = solveA(x, y + new_dim, new_dim, cand[2]);
    v[2] += calc_sum(x, y + new_dim, x + new_dim - 1, y + 2 * new_dim - 1);
    v[3] = solveA(x + new_dim, y, new_dim, cand[3]);
    v[3] += calc_sum(x + new_dim, y, x + 2 * new_dim - 1, y + new_dim - 1);
    v[4] = solveA(x + new_dim, y + new_dim, new_dim, cand[4]);
    v[4] += calc_sum(x + new_dim, y + new_dim, x + 2 * new_dim - 1, y + 2 * new_dim - 1);
    int index = 0;
    for(int i = 1; i < 5; ++i)
        if(v[i] > v[index])
            index = i;
    rez.emplace_back(index);
    for(int x : cand[index])
        rez.emplace_back(x);
    return v[index];
}

int solveB(int x, int y, int dim, int itr, vector < int > &rez, bool flag) {
    if(dim == 1)
        return 0;
    int new_dim = dim >> 1;
    vector < int > v(5, -1);
    vector < vector < int > > cand(5);
    bool new_flag = flag;
    if(!flag && A[itr] != 1)
        new_flag = true;
    v[1] = solveB(x, y, new_dim, itr + 1, cand[1], new_flag);
    if(new_flag)
        v[1] += calc_sum(x, y, x + new_dim - 1, y + new_dim - 1);
    new_flag = flag;
    if(!flag && A[itr] != 2)
        new_flag = true;
    v[2] = solveB(x, y + new_dim, new_dim, itr + 1, cand[2], new_flag);
    if(new_flag)
        v[2] += calc_sum(x, y + new_dim, x + new_dim - 1, y + 2 * new_dim - 1);
    new_flag = flag;
    if(!flag && A[itr] != 3)
        new_flag = true;
    v[3] = solveB(x + new_dim, y, new_dim, itr + 1, cand[3], new_flag);
    if(new_flag)
        v[3] += calc_sum(x + new_dim, y, x + 2 * new_dim - 1, y + new_dim - 1);
    new_flag = flag;
    if(!flag && A[itr] != 4)
        new_flag = true;
    v[4] = solveB(x + new_dim, y + new_dim, new_dim, itr + 1, cand[4], new_flag);
    if(new_flag)
        v[4] += calc_sum(x + new_dim, y + new_dim, x + 2 * new_dim - 1, y + 2 * new_dim - 1);
    int index = 0;
    for(int i = 1; i < 5; ++i)
        if(v[i] > v[index])
            index = i;
    rez.emplace_back(index);
    for(int x : cand[index])
        rez.emplace_back(x);
    return v[index];
}

int main() {
    int task, N;
    fin >> task >> N;
    N = (1 << N);
    a.resize(N + 1);
    dp = vector < vector < int > >(N + 1, vector < int >(N + 1));
    for(int i = 1; i <= N; ++i) {
        fin >> a[i];
        a[i] = '0' + a[i];
        for(int j = 1; j <= N; ++j) {
            int add = a[i][j] - '0';
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + add;
        }
    }
    fout << solveA(1, 1, N, A) + solveB(1, 1, N, 0, B, false) << '\n';
    if(task == 2) {
        int p = 0, M = A.size();
        while(p < M && A[p] == B[p])
            ++p;
        if(p < M && A[p] < B[p]) {
            for(int x : A)
                fout << x << ' ';
            fout << '\n';
            for(int x : B)
                fout << x << ' ';
        }
        else {
            for(int x : B)
                fout << x << ' ';
            fout << '\n';
            for(int x : A)
                fout << x << ' ';
        }
    }
}