#include <bits/stdc++.h>
#include "mars.h"
using namespace std;
//dengyaotriangle!

string process(vector<vector<string>> a, int i, int j, int k, int n) {
    if (i == 2 * (n - k - 1) && j == 2 * (n - k - 1)) {
        int len = k * 2 + 3;
        vector<vector<char>> mp(len, vector<char>(len, 0));
        vector<int> fa(len * len);
        iota(fa.begin(), fa.end(), 0);
        function<int(int)> grt = [&](int u) {
            return fa[u] == u ? u : fa[u] = grt(fa[u]);
        };
        auto tr = [&](int i, int j) {
            return i * len + j;
        };
        int ans = 0;
        auto tm = [&](int i, int j) {
            i = grt(i), j = grt(j);

            if (i != j)
                fa[i] = j, ans--;
        };

        if (k == 0) {
            for (int i = 0; i < 3; i++)
                for (int j = 0; j < 3; j++)
                    mp[i][j] = a[i][j][0] - '0';
        } else {
            for (int i = 0; i < 2; i++)
                for (int j = 0; j < 2; j++)
                    mp[i][j] = a[i][j][0] - '0';

            for (int t = 0; t < 2; t++) {
                for (int i = 1, j = 2, s = 0; j < len; j += i == 0, i ^= 1, s++) {
                    mp[i + t][j] = a[t][2][s] - '0';
                }
            }

            for (int t = 0; t < 2; t++) {
                for (int j = 1, i = 2, s = 0; i < len; i += j == 0, j ^= 1, s++) {
                    mp[i][j + t] = a[2][t][s] - '0';
                }
            }

            for (int i = 99; i >= 88; i--)
                ans = ans * 2 + a[2][2][i] - '0';
        }

        for (int i = 0; i < len; i++)
            for (int j = 0; j < len; j++)
                ans += mp[i][j]; //,cerr<<int(mp[i][j])<<" \n"[j==len-1];

        for (int i = 0; i < len; i++)
            for (int j = 0; j < len; j++) {
                if (mp[i][j]) {
                    if (i + 1 < len && mp[i + 1][j]) {
                        tm(tr(i, j), tr(i + 1, j));
                    }

                    if (j + 1 < len && mp[i][j + 1]) {
                        tm(tr(i, j), tr(i, j + 1));
                    }
                }
            }

        if (k) { //decode!
            int rp = -1;
            int z = 0;
            stack<int> stk;

            for (int i = 2, j = len - 1; i <= len; i += j == 2, j -= j > 2) {
                if (i == len || !mp[i][j]) {
                    if (rp != -1) {
                        if (a[2][2][z] == '1') {
                            int u = stk.top();
                            stk.pop();
                            tm(u, rp);
                        }

                        if (a[2][2][z + 1] == '1') {
                            stk.push(rp);
                        }

                        z += 2;
                    }

                    rp = -1;
                } else
                    rp = tr(i, j);
            }
        }

        if (k == n - 1) { //ret
            string x;

            for (int i = 0; i < 100; i++, ans /= 2)
                x += ans % 2 + '0';

            return x;
        } else { //encode!
            string ret;
            int rp = -1;
            vector<int> vec;

            for (int i = 0, j = len - 1; i <= len; i += !j, j -= !!j) {
                if (i == len || !mp[i][j]) {
                    if (rp != -1) {
                        vec.push_back(rp);
                    }

                    rp = -1;
                } else
                    rp = tr(i, j);
            }

            for (int i = 0; i < vec.size(); i++) {
                string u = "00";

                for (int j = 0; j < i; j++) {
                    if (grt(vec[i]) == grt(vec[j]))
                        u[0] = '1';
                }

                for (int j = i + 1; j < vec.size(); j++) {
                    if (grt(vec[i]) == grt(vec[j]))
                        u[1] = '1';
                }

                ans -= u[0] == '0';
                ret += u;
            }

            while (ret.size() < 88)
                ret += '0';

            for (int i = 88; i < 100; i++, ans /= 2)
                ret += ans % 2 + '0';

            return ret;
        }
    } else if (i == 2 * (n - k - 1)) {
        string ret = a[2][0];

        if (k == 0)
            ret = a[2][1][0] + ret;

        ret = a[0][1][0] + (a[0][0][0] + (a[1][1][0] + (a[1][0][0] + ret)));

        while (ret.size() > 100)
            ret.pop_back();

        return ret;
    } else if (j == 2 * (n - k - 1)) {
        string ret = a[0][2];

        if (k == 0)
            ret = a[1][2][0] + ret;

        ret = a[1][0][0] + (a[0][0][0] + (a[1][1][0] + (a[0][1][0] + ret)));

        while (ret.size() > 100)
            ret.pop_back();

        return ret;
    } else
        return a[0][0];
}