#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
array<int, 4> get(int N, int K, int i, int j) {
int M = N - 2 * K;
int x = N / M;
int y = N % M;
if (i < y && j < y) {
return {i * (x + 1), j * (x + 1), x + 1, x + 1};
} else if (i < y) {
return {i * (x + 1), y * (x + 1) + (j - y) * x, x + 1, x};
} else if (j < y) {
return {y * (x + 1) + (i - y) * x, j * (x + 1), x, x + 1};
} else {
return {y * (x + 1) + (i - y) * x, y * (x + 1) + (j - y) * x, x, x};
}
}
constexpr int dx[] = {0, 0, -1, 1};
constexpr int dy[] = {-1, 1, 0, 0};
int cnt(vector<vector<char>> &g) {
int n = g.size(), ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == '0') {
continue;
}
ans++;
queue<pair<int, int>> q;
g[i][j] = '0';
q.emplace(i, j);
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (min(nx, ny) >= 0 && max(nx, ny) < n && g[nx][ny] == '1') {
g[nx][ny] = '0';
q.emplace(nx, ny);
}
}
}
}
}
return ans;
}
string process(vector<vector<string>> a, int X, int Y, int K, int N) {
vector g(2 * N + 1, vector<char>(2 * N + 1));
for (int i = X; i < X + 3; i++) {
for (int j = Y; j < Y + 3; j++) {
auto [s, t, u, v] = get(2 * N + 1, K, i, j);
for (int x = s; x < s + u; x++) {
for (int y = t; y < t + v; y++) {
assert(x <= 2 * N && y <= 2 * N);
g[x][y] = a[i - X][j - Y][v * (x - s) + (y - t)];
}
}
}
}
string ans(100, '0');
if (K == N - 1) {
int land = cnt(g);
for (int i = 0; i < 30; i++) {
if (land >> i & 1) {
ans[i] = '1';
}
}
} else {
auto [s, t, u, v] = get(2 * N + 1, K + 1, X, Y);
for (int i = s; i < s + u; i++) {
for (int j = t; j < t + v; j++) {
assert(i <= 2 * N && j <= 2 * N);
ans[v * (i - s) + (j - t)] = g[i][j];
}
}
}
return ans;
}
