#include <bits/stdc++.h>
#include "mars.h"
using namespace std;
#define SIZE 100
#define MAXL 45
string collect(const vector<vector<string>> &a, int k) {
string ans;
for (int i = 0; i < 2 * k + 3; i++) {
if (i < 2 * k + 1) {
ans += a[0][0].substr(i * (2 * k + 1), 2 * k + 1) + a[0][1][i * (2 * k + 1) + 2 * k] + a[0][2][i * (2 * k + 1) + 2 * k];
} else {
int j = i - 2 * k;
ans += a[j][0].substr((2 * k) * (2 * k + 1), 2 * k + 1) + a[j][1][(2 * k) * (2 * k + 1) + 2 * k] + a[j][2][(2 * k) * (2 * k + 1) + 2 * k];
}
}
return ans + string(SIZE - ans.size(), '0');
}
vector<vector<map<int, int>>> get_trans(int n) {
vector<vector<map<int, int>>> trans(2 * n + 1, vector<map<int, int>>(2 * n + 1));
int sz = 2 * n + 1;
for (int x = 0; ; x++) {
int sx = max(0, sz - 9 * (x + 1));
int tx = sx == 0 ? 0 : 2 - x;
for (int y = 0; ; y++) {
int sy = max(0, sz - 9 * (y + 1));
int ty = sy == 0 ? 0 : 2 - y;
int cnt = 0, cx = sx, cy = sy;
while (cx != tx || cy != ty) {
int nx = cx - 2 * (cx != tx);
int ny = cy - 2 * (cy != ty);
trans[nx][ny][cnt] = ((cx != tx) << 1) | (cy != ty);
cx = nx;
cy = ny;
cnt++;
}
if (sy == 0) break;
}
if (sx == 0) break;
}
return trans;
}
int last_call(int n, int i, int j) { return min((2 * n - i) / 2, (2 * n - j) / 2) - 1; }
string transfer(const vector<vector<string>> &a, int i, int j, int k, int n) {
switch (get_trans(n)[i][j][k - 4]) {
case 0: return a[0][0];
case 1: return a[0][2];
case 2: return a[2][0];
case 3: return a[2][2];
}
}
string cc(const vector<vector<string>> &a, int n) {
int sz = 2 * n + 1;
vector<vector<bool>> grid(sz, vector<bool>(sz));
if (n > 4) {
for (int x = 0; ; x++) {
int sx = max(0, sz - 9 * (x + 1));
int tx = sx == 0 ? 0 : 2 - x;
for (int y = 0; ; y++) {
int sy = max(0, sz - 9 * (y + 1));
int ty = sy == 0 ? 0 : 2 - y;
int w = sy == 0 ? (sz - 1) % 9 + 1 : 9;
int h = sx == 0 ? (sz - 1) % 9 + 1 : 9;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
grid[sx + i][sy + j] = a[tx][ty][i * 9 + j] == '1';
}
}
if (sy == 0) break;
}
if (sx == 0) break;
}
} else {
string g = collect(a, n - 1);
for (int i = 0; i < sz; i++)
for (int j = 0; j < sz; j++)
grid[i][j] = g[sz * i + j] == '1';
}
vector<vector<bool>> vis(sz, vector<bool>(sz));
int cnt = 0;
for (int i = 0; i < sz; i++) {
for (int j = 0; j < sz; j++) {
if (vis[i][j] || !grid[i][j]) continue;
cnt++;
queue<pair<int, int>> q;
q.emplace(i, j);
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
if (vis[x][y] || !grid[x][y]) continue;
vis[x][y] = true;
if (x > 0)
q.emplace(x - 1, y);
if (x < sz - 1)
q.emplace(x + 1, y);
if (y > 0)
q.emplace(x, y - 1);
if (y < sz - 1)
q.emplace(x, y + 1);
}
}
}
string ans(SIZE, '0');
for (int i = 0; i < SIZE; i++) {
if (cnt & 1)
ans[i] = '1';
cnt >>= 1;
}
return ans;
}
string process(vector<vector<string>> a, int i, int j, int k, int n) {
if (k == n - 1)
return cc(a, n);
if (k <= 3)
return collect(a, k);
return transfer(a, i, j, k, n);
assert(false);
}
