#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<array<int,2>>> reqs(int n){
n*=2;
n++;
n-=8;
vector<int>temp;
for(int i = 0;i<n;i++){
if(i%9==0||i==n-1){
temp.push_back(i);
}
}
//must ensure atleast 5x5 (rn 3x3 for test)
if(temp.size()<3){
temp.insert(temp.begin()+1,1);
}
vector<vector<array<int,2>>>ans;
for(int i : temp){
vector<array<int,2>>cur;
for(int j : temp){
cur.push_back({i,j});
}
ans.push_back(cur);
}
return ans;
}
string process(vector<vector<string>> a, int i, int j, int k, int n) {
if(k<=n-2){
//routing phase
int curlen = 2*k+3;
if(curlen<=9){
//still making 9x9s for each
int prevlen = 2*k+1;
char grid[curlen][curlen];
bool vis[curlen][curlen];
for(int i = 0;i<curlen;i++){
for(int j = 0;j<curlen;j++){
vis[i][j]=0;
}
}
//current grid made now extend to curlen
///fill using all in order to account for corner(literally) cases
for(int i = 0;i<3;i++){
for(int j = 0;j<3;j++){
for(int curi = 0;curi<prevlen;curi++){
for(int curj = 0;curj<prevlen;curj++){
int x = curi+i;
int y = curj+j;
if(!vis[x][y]){
vis[x][y]=1;
grid[x][y]=(a[i][j][curi*prevlen+curj]=='1');
}
}
}
}
}
string ret(100,'0');
int ind = 0;
for(int i = 0;i<curlen;i++){
for(int j = 0;j<curlen;j++){
ret[ind++]=(grid[i][j] ? '1' : '0');
}
}
return ret;
}
else{
//exact 9x9s made for all
//now must put them in correct place
int cntshift = curlen-11;
if(i==0&&j==0){
return a[0][0];
}
vector<vector<array<int,2>>>tars = reqs(n);
for(int x = 0;x<tars.size();x++){
for(int y = 0;y<tars.size();y++){
array<int,2>pay = tars[x][y];
array<int,2>curr = {max(x,pay[0]-cntshift),max(y,pay[1]-cntshift)};
cntshift+=2;
array<int,2>nx = {max(x,pay[0]-cntshift),max(y,pay[1]-cntshift)};
cntshift-=2;
if(nx==(array<int,2>){i,j}){
//next position of this one is here
array<int,2>h = {curr[0]-i,curr[1]-j};
if(max(h[0],h[1])<=2&&min(h[0],h[1])>=0){
//possible
return a[h[0]][h[1]];
}
}
}
}
}
}
else if(k==n-2){
//second last phase. all bits should be where they need to be
int len = n*2+1;
vector<vector<array<int,2>>>pos;
if(len>=15){
//figure out using function
pos=reqs(n);
}
else{
for(int i = 0;i<5;i++){
vector<array<int,2>>cur;
for(int j = 0;j<5;j++){
cur.push_back({i,j});
}
pos.push_back(cur);
}
}
//pos has all the inds now must do the REAL thingy
if(i%2||j%2){
//odd not required.
return string(100,'0');
}
}
else{
//last phase (temporary pure data)
int len = n*2+1;
vector<vector<array<int,2>>>pos;
if(len>9){
//figure out using function
pos=reqs(n);
}
else{
for(int i = 0;i<5;i++){
vector<array<int,2>>cur;
for(int j = 0;j<5;j++){
cur.push_back({i,j});
}
pos.push_back(cur);
}
}
bool grid[len][len];
if(k>4){
for(int x = 0;x<pos.size();x++){
for(int y = 0;y<pos.size();y++){
array<int,2>curr = pos[x][y];
for(int curi = 0;curi<9;curi++){
for(int curj = 0;curj<9;curj++){
grid[curi+curr[0]][curj+curr[1]]=(a[x][y][curi*9+curj]=='1');
}
}
}
}
}
else{
//all have len-2
int prevlen = len-2;
bool vis[len][len];
for(int i = 0;i<len;i++){
for(int j = 0;j<len;j++){
vis[i][j]=0;
}
}
for(int i = 0;i<3;i++){
for(int j = 0;j<3;j++){
for(int curi = 0;curi<prevlen;curi++){
for(int curj = 0;curj<prevlen;curj++){
int x = curi+i;
int y = curj+j;
if(!vis[x][y]){
vis[x][y]=1;
grid[x][y]=(a[i][j][curi*prevlen+curj]=='1');
}
}
}
}
}
}
//grid reformed, now must count islands
bool vis[len][len];
for(int i = 0;i<len;i++){
for(int j = 0;j<len;j++){
vis[i][j]=0;
}
}
int ans = 0;
for(int i = 0;i<len;i++){
for(int j = 0;j<len;j++){
if(grid[i][j]&&!vis[i][j]){
//new component
ans++;
queue<array<int,2>>q;
q.push({i,j});
vis[i][j]=1;
while(!q.empty()){
auto [x,y] = q.front();
q.pop();
if(x-1>=0&&grid[x-1][y]&&!vis[x-1][y]){
vis[x-1][y]=1;
q.push({x-1,y});
}
if(x+1<len&&grid[x+1][y]&&!vis[x+1][y]){
vis[x+1][y]=1;
q.push({x+1,y});
}
if(y-1>=0&&grid[x][y-1]&&!vis[x][y-1]){
vis[x][y-1]=1;
q.push({x,y-1});
}
if(y+1<len&&grid[x][y+1]&&!vis[x][y+1]){
vis[x][y+1]=1;
q.push({x,y+1});
}
}
}
}
}
string fin(100,'0');
for(int i = 0;i<30;i++){
if((1<<i)&ans){
fin[i]='1';
}
}
return fin;
}
return string(100,'0');
}
