#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
int cnt;
vector<int> f;
DSU(int n) : cnt(n), f(n) { iota(f.begin(), f.end(), 0); }
int leader(int u) {
while (u != f[u]) {
u = f[u] = f[f[u]];
}
return u;
}
bool unionize(int u, int v) {
u = leader(u);
v = leader(v);
if (u == v) return false;
f[u] = v;
cnt--;
return true;
}
int count() {
return cnt;
}
bool same(int u, int v) {
return leader(u) == leader(v);
}
};
int string_to_int(string s) {
int res = 0;
for (int i = 0; i < s.size(); i++) {
res += (s[i] - '0') * (1 << i);
}
return res;
}
string int_to_string(int x, int length) {
string res;
for (int i = 0; i < length; i++) {
res.push_back('0' + (x & 1));
x >>= 1;
}
return res;
}
string _process(vector<vector<string>> a, int i, int j, int k, int n)
{
int m = 2 * (n - k - 1);
if (i != m && j != m) return a[0][0];
if (i < j) {
string s(100, '0');
s[0] = a[0][0][0];
s[1] = a[0][1][0];
for (int x = 2; x < 50; x++) {
s[x] = a[0][2][x - 2];
}
s[50] = a[1][0][0];
s[51] = a[1][1][0];
for (int x = 52; x < 100; x++) {
s[x] = a[1][2][x - 52];
}
return s;
}
if (i > j) {
string s(100, '0');
s[0] = a[0][0][0];
s[1] = a[1][0][0];
for (int x = 2; x < 50; x++) {
s[x] = a[2][0][x - 2];
}
s[50] = a[0][1][0];
s[51] = a[1][1][0];
for (int x = 52; x < 100; x++) {
s[x] = a[2][1][x - 52];
}
return s;
}
int d = 2 * n + 1 - m;
vector<array<int, 2>> dxy = { {-1, 0}, {+1, 0}, {0, -1}, {0, +1} };
auto valid = [&](int x, int y) {
if (x < 0 || x >= d || y < 0 || y >= d) return false;
return true;
};
auto neighbour = [&](int x, int y) {
vector<array<int, 2>> res;
for (auto [dx, dy] : dxy) {
if (valid(x + dx, y + dy)) res.push_back({x + dx, y + dy});
}
return res;
};
auto [mp, cnt, id] = [&]() -> tuple<vector<vector<bool>>, int, vector<vector<int>>> {
vector<vector<bool>> mp(d, vector<bool>(d, 0));
for (int x = 0; x < 2; x++) {
for (int y = 0; y < 2; y++) {
mp[x][y] = a[x][y][0] - '0';
}
}
for (int x = 0; x < 2; x++) {
for (int y = 2; y < d; y++) {
mp[x][y] = a[x][2][y - 2] - '0';
mp[x + 1][y] = k == 0 ? a[x + 1][2][y - 2] - '0' : a[x][2][50 + y - 2] - '0';
}
}
for (int y = 0; y < 2; y++) {
for (int x = 2; x < d; x++) {
mp[x][y] = a[2][y][x - 2] - '0';
mp[x][y + 1] = k == 0 ? a[2][y + 1][x - 2] - '0' : a[2][y][50 + x - 2] - '0';
}
}
int cnt = 0;
vector<vector<int>> id(d, vector<int>(d, -1));
for (int x = 0; x < d; x++) {
for (int y = 0; y < d; y++) {
if (mp[x][y]) {
id[x][y] = cnt++;
}
}
}
return {mp, cnt, id};
}();
DSU dsu(cnt + 1);
for (int x = 0; x < d; x++) {
for (int y = 0; y < d; y++) {
for (auto [xx, yy] : neighbour(x, y)) {
if (mp[x][y] && mp[xx][yy]) {
dsu.unionize(id[x][y], id[xx][yy]);
}
}
}
}
auto [config, seq] = [&] {
vector<array<int, 2>> config;
vector<int> seq;
for (int x = d - 1; x >= 2; x--) if (mp[x][2] && (x == d - 1 || !mp[x + 1][2])) config.push_back({x, 2});
for (int y = 3; y < d; y++) if (mp[2][y] && !mp[2][y - 1]) config.push_back({2, y});
for (int i = 0; i < config.size(); i++) seq.push_back(string_to_int(a[2][2].substr(2 * i, 2)));
if (k == 0 && !seq.empty()) seq[0] = 0;
return make_pair(config, seq);
}();
vector<array<int, 2>> stk;
for (int i = 0; i < config.size(); i++) {
if (seq[i] & 1) { // close
auto [x, y] = config[i];
auto [xx, yy] = stk.back();
dsu.unionize(id[x][y], id[xx][yy]);
stk.pop_back();
}
if (seq[i] & 2) { // open
stk.push_back(config[i]);
}
}
int fetch = string_to_int(a[2][2].substr(85));
if (k == n - 1) {
return int_to_string(dsu.count() - 1 + fetch, 100);
} else {
string res;
vector<array<int, 2>> config;
for (int x = d - 1; x >= 0; x--) if (mp[x][0] && (x == d - 1 || !mp[x + 1][0])) config.push_back({x, 0});
for (int y = 1; y < d; y++) if (mp[0][y] && !mp[0][y - 1]) config.push_back({0, y});
for (int i = 0; i < config.size(); i++) {
bool close = false;
bool open = false;
auto [x, y] = config[i];
for (int j = 0; j < config.size(); j++) {
auto [xx, yy] = config[j];
if (dsu.same(id[x][y], id[xx][yy])) {
if (j < i) close = true;
if (i < j) open = true;
}
}
res.push_back('0' + close);
res.push_back('0' + open);
}
for (auto [x, y] : config) {
dsu.unionize(id[x][y], cnt);
}
while (res.size() < 85) res.push_back('0');
res += int_to_string(dsu.count() - 1 + fetch, 15);
return res;
}
}
string process(vector<vector<string>> a, int i, int j, int k, int n) {
string s = _process(a, i, j, k, n);
// cout << k << ' ' << i << ' ' << j << ": " << s << '\n';
return s;
}
