#include "mars.h"
#include<set>
#include<map>
#include<string>
#include<math.h>
#include<queue>
#include<stack>
#include<iomanip>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
vvll g;
vvll vis;
void dfs(ll x, ll y, ll n) {
vis[x][y] = true;
if (x > 0 && g[x-1][y] == 1 && !vis[x - 1][y]) {
dfs(x - 1, y, n);
}
if (x < n - 1 && g[x+1][y] == 1 && !vis[x + 1][y]) {
dfs(x + 1, y, n);
}
if (y > 0 && g[x][y - 1] == 1 && !vis[x][y - 1]) {
dfs(x, y - 1, n);
}
if (y < n - 1 && g[x][y + 1] == 1 && !vis[x][y+1]) {
dfs(x, y + 1, n);
}
}
string build(ll s) {
string ans = "";
for (ll i = 0; i <= 30; i++) {
if (s & (1LL << i)) {
ans += "1";
}
else {
ans += "0";
}
}
return ans;
}
string calc(string ans, ll n) {
g.clear();
vis.clear();
g.resize(n, vll(n));
vis.resize(n, vll(n));
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
g[i][j] = ans[i * n + j] -'0';
}
}
ll s = 0;
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
if (!vis[i][j] && g[i][j] == 1) {
s++;
dfs(i, j, n);
}
}
}
string sol = build(s);
while (sol.size() < 100) {
sol += "0";
}
return sol;
}
std::string process(std::vector <std::vector<std::string>> a, int i, int j, int k, int n)
{
ll prev_sz = 2 * (k - 1) + 3;
string ans = "";
if (k == 0) {
for (ll i = 0; i < 3; i++) {
for (ll j = 0; j < 3; j++) {
ans += a[i][j][0];
}
}
}
else {
vpll ind = { {0,0}, {0,2}, {2,0}, {2,2} };
vector<vector<string>> s(4);
for (ll i = 0; i < 4; i++) {
pll now = ind[i];
ll x = now.first, y = now.second;
string val = a[x][y];
for (ll j = (x == 2 ? prev_sz - 1 : 1); j <= prev_sz; j++) {
s[i].push_back(val.substr(j * prev_sz - (y == 2 ? 2 : prev_sz), (y == 2 ? 2 : prev_sz)));
}
}
for (ll i = 0; i < s[0].size(); i++) {
ans += s[0][i] + s[1][i];
}
for (ll i = 0; i < s[2].size(); i++) {
ans += s[2][i] + s[3][i];
}
}
while (ans.size() < 100) {
ans += "0";
}
if (k < n - 1) {
return ans;
}
else {
return calc(ans, 2*n + 1);
}
}
