#include <bits/stdc++.h>
#include "mars.h"
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;

#define x first
#define y second
#define mkp make_pair
#define pb push_back
typedef pair<int, int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

string expand(string s) {
    while (s.size() < 100)
        s += '0';

    return s;
}

string enc(vi o, int num) {
    int siz = o.size();
    string res;
    For(i, 0, siz - 1) {
        int j = i;

        if (!o[i])
            continue;

        while (j + 1 < siz && o[i] == o[j + 1])
            ++j;

        bool l = 0, r = 0;
        Rep(k, i - 1, 0)l |= (o[k] == o[i]);
        For(k, j + 1, siz - 1)r |= (o[k] == o[i]);
        res += (l + '0');
        res += (r + '0');
        i = j;
    }
    res = expand(res);

    For(i, 0, 9)if (num >> i & 1)
        res[i + 90] = '1';

    return res;
}

vi dec(string s) {
    vi res, stk;
    int c = 0;

    for (int i = 0; i < 90; i += 2) {
        bool l = (s[i] & 1), r = (s[i + 1] & 1);

        if (!l && !r)
            res.pb(++c);

        if (!l && r)
            ++c, res.pb(c), stk.pb(c);

        if (l && !r)
            res.pb(stk.back()), stk.pop_back();

        if (l & r)
            res.pb(stk.back());
    }

    return res;
}

int n, mp[55][55], fa[55 * 55], allc;
inline int P(int x, int y) {
    return x * (2 * n + 1) + y;
}
inline int getf(int x) {
    while (x != fa[x])
        x = fa[x] = fa[fa[x]];

    return x;
}
inline void merge(int x, int y) {
    x = getf(x), y = getf(y), fa[x] = y;
}

bool vis[55 * 55];
int col[55][55];
int getcnt(int x) {
    For(i, 0, allc - 1) vis[i] = 0;

    For(i, 0, 2 * n) For(j, 0, 2 * n) if (i == x || j == x)
        vis[getf(P(i, j))] = 1;

    int res = 0;

    For(i, 0, 2 * n) For(j, 0, 2 * n) if (mp[i][j] && getf(P(i, j)) == P(i, j) && !vis[P(i, j)])
        ++res;

    return res;
}
int getres() {
    int res = 0;

    For(i, 0, 2 * n) For(j, 0, 2 * n) if (mp[i][j] && getf(P(i, j)) == P(i, j))
        ++res;

    return res;
}

string process(vector<vector<string>>a, int x, int y, int k, int N) {
    n = N;

    if (x < 2 * (n - k - 1) && y < 2 * (n - k - 1))
        return a[0][0];

    if (y != 2 * (n - k - 1)) {
        string res;
        res += a[0][0][0];
        res += a[1][0][0];
        For(i, 0, 2 * k)res += a[2][0][i];
        res += a[0][1][0], res += a[1][1][0];
        For(i, 0, 2 * k)res += a[2][1][i];
        return expand(res);
    }

    if (x != 2 * (n - k - 1)) {
        string res;
        res += a[0][0][0];
        res += a[0][1][0];
        For(i, 0, 2 * k)res += a[0][2][i];
        res += a[1][0][0], res += a[1][1][0];
        For(i, 0, 2 * k)res += a[1][2][i];
        return expand(res);
    }

    //  cout<<x<<" "<<y<<" "<<k<<" "<<N<<endl;
    //  For(i,0,2)For(j,0,2)cout<<a[i][j]<<"\n";puts("----");

    // clear:
    allc = (2 * n + 1) * (2 * n + 1);
    For(i, 0, 2 * n)For(j, 0, 2 * n)col[i][j] = mp[i][j] = 0;
    For(i, 0, allc - 1)fa[i] = i;

    // k=0:
    if (k == 0) {
        For(i, 0, 2)For(j, 0, 2)mp[x + i][y + j] = a[i][j][0] & 1;
        For(i, x, x + 2)For(j, y, y + 2)

        if (mp[i][j]) {
            if (mp[i + 1][j])
                merge(P(i, j), P(i + 1, j));

            if (mp[i][j + 1])
                merge(P(i, j), P(i, j + 1));
        }

        if (x == 0 && y == 0) {
            string res(100, '0');
            int x = getres();
            For(i, 0, 9) res[i] = '0' + (x >> i & 1);
            return res;
        }

        vi tmp;
        Rep(i, 2 * k + 4, 0)tmp.pb(mp[x + i][y]*getf(P(x + i, y)));
        For(i, 1, 2 * k + 4)tmp.pb(mp[x][y + i]*getf(P(x, y + i)));
        return enc(tmp, getcnt(x));
    }

    // getlst:
    vi lst = dec(a[2][2]);
    int lstres = 0;

    For(i, 0, 9) if (a[2][2][i + 90] & 1)
        lstres |= (1 << i);

    // getmap:
    For(i, 0, 1)For(j, 0, 1)mp[x + i][y + j] = a[i][j][0] & 1;
    For(i, 0, 2 * k) {
        For(j, 0, 1) {
            mp[x + i + 2][y + j] = a[2][j][i] & 1;
            mp[x + j][y + i + 2] = a[j][2][i] & 1;
        }
        mp[x + i + 2][y + 2] = a[2][1][i + 2 * k + 1] & 1;
        mp[x + 2][y + i + 2] = a[1][2][i + 2 * k + 1] & 1;
    }

    // getlink:
    For(i, 0, 2 * n)For(j, 0, 2 * n)

    if (mp[i][j]) {
        if (mp[i + 1][j])
            merge(P(i, j), P(i + 1, j));

        if (mp[i][j + 1])
            merge(P(i, j), P(i, j + 1));
    }

    vector<pii>p;
    Rep(i, 2 * k + 2, 0)p.pb(mkp(x + i + 2, y + 2));
    For(i, 1, 2 * k + 2)p.pb(mkp(x + 2, y + i + 2));
    int np = 0, siz = p.size();
    For(i, 0, siz - 1) {
        int j = i, x = p[i].x, y = p[i].y;

        if (!mp[x][y])
            continue;

        col[x][y] = lst[np];

        while (j + 1 < siz && mp[p[j + 1].x][p[j + 1].y])
            ++j, col[p[j].x][p[j].y] = lst[np];

        i = j;
        ++np;
    }

    //  cout<<"lst: "<<lstres<<endl;
    //  For(i,0,2*n)For(j,0,2*n)cout<<mp[i][j]<<" \n"[j==2*n];
    //  for(auto t:p)cout<<t.x<<" "<<t.y<<endl;
    //  For(i,0,2*n)For(j,0,2*n)cout<<col[i][j]<<" \n"[j==2*n];

    For(i, 0, siz - 1) {
        int c1 = col[p[i].x][p[i].y];

        if (!c1)
            continue;

        For(j, i + 1, siz - 1) {
            int c2 = col[p[j].x][p[j].y];

            if (c1 == c2)
                merge(P(p[i].x, p[i].y), P(p[j].x, p[j].y));
        }
    }

    if (!x && !y) {
        //      For(i,0,2*n)For(j,0,2*n)cout<<getf(P(i,j))*mp[i][j]<<" \n"[j==2*n];
        string res(100, '0');
        int x = getres() + lstres;
        For(i, 0, 9) res[i] = '0' + (x >> i & 1);
        return res;
    }

    vi tmp;
    Rep(i, 2 * k + 4, 0)tmp.pb(mp[x + i][y]*getf(P(x + i, y)));
    For(i, 1, 2 * k + 4)tmp.pb(mp[x][y + i]*getf(P(x, y + i)));
    return enc(tmp, lstres + getcnt(x));
}