#include "mars.h"
#include<bits/stdc++.h>
using namespace std;
int N;
int v[100][100];
int refId[100][100];
vector< pair<int,int> > refs[10000];
int newGrpId[100][100];
int grpId;
bool vis[100][100];
int freq[10000];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
bool valid(int x, int y) {
return ((x>=0 && y>=0 && x<=2*N && y<=2*N) && (v[x][y] == 1 && !vis[x][y]));
}
void dfs(int x, int y) {
newGrpId[x][y] = grpId;
vis[x][y] = true;
for(int i=0; i<4; i++) {
if(valid(x+dx[i], y+dy[i])) {
dfs(x+dx[i], y+dy[i]);
}
}
if(refId[x][y]!=-1) {
for(auto i:refs[refId[x][y]]) {
if(valid(i.first, i.second)) dfs(i.first, i.second);
}
}
}
string inttobin(int v, int len) {
string rv = "";
for(int i=0; i<len; i++) {
if((v>>i)%2) rv += "1";
else rv += "0";
}
return rv;
}
std::string process(std::vector <std::vector<std::string>> a, int i, int j, int k, int n)
{
N = n;
// case handling
int m = 2*(n-k-1);
if(i == m && j == m) {
// find v
for(int I=0; I<=2*n; I++) {
for(int J=0; J<=2*n; J++) {
v[I][J] = -1;
refId[I][J] = -1;
vis[I][J] = false;
}
}
string d1 = a[1][0].substr(1, k*3);
string d2 = a[2][0].substr(1, k*3);
string r1 = a[0][1].substr(1, k*3);
string r2 = a[0][2].substr(1, k*3);
int ptr = 0;
for(int I=i+3; I<=2*n; I+=2) {
for(int J=j; J<=j+2; J++) {
v[I][J] = d1[ptr] - '0';
ptr++;
}
}
ptr = 0;
for(int I=i+4; I<=2*n; I+=2) {
for(int J=j; J<=j+2; J++) {
v[I][J] = d2[ptr] - '0';
ptr++;
}
}
ptr = 0;
for(int J=j+3; J<=2*n; J+=2) {
for(int I=i; I<=i+2; I++) {
v[I][J] = r1[ptr] - '0';
ptr++;
}
}
ptr = 0;
for(int J=j+4; J<=2*n; J+=2) {
for(int I=i; I<=i+2; I++) {
v[I][J] = r2[ptr] - '0';
ptr++;
}
}
for(int I=i; I<=i+2; I++) for(int J=j; J<=j+2; J++) v[I][J] = a[I-i][J-j][0] - '0';
// decode previous string
int ans = 0;
if(k > 0) {
string ansstr = a[2][2].substr(1, 10);
for(int I=0; I<10; I++) {
if(ansstr[I]=='1') ans += (1<<I);
}
vector< pair<int, int> > L; L.clear();
vector< pair<int, int> > L2; L2.clear();
vector<int> rel; rel.clear();
for(int I=2*n; I>=i+2; I--) L.push_back({I, j+2});
for(int J=j+3; J<=2*n; J++) L.push_back({i+2, J});
int Prev = 0;
int cnt = 0;
for(auto c:L) {
if(Prev == 0 && v[c.first][c.second] == 1) {
refId[c.first][c.second] = cnt;
L2.push_back(c);
cnt++;
}
Prev = v[c.first][c.second];
}
string relstr = a[2][2].substr(11, 1e9);
stack<int> stk;
int tmpcnt = -1;
for(int I=0; I<relstr.length(); I++) {
if(relstr[I] == '1') {
if(tmpcnt+1 == cnt) break;
tmpcnt++;
stk.push(tmpcnt);
} else {
stk.pop();
refId[L2[tmpcnt].first][L2[tmpcnt].second] = stk.top();
}
}
for(int I=0; I<cnt; I++) refs[I].clear();
for(auto c:L) {
if(refId[c.first][c.second] != -1) {
refs[refId[c.first][c.second]].push_back(c);
}
}
}
grpId = 0;
for(int I=i; I<=2*n; I++) {
for(int J=j; J<=2*n; J++) {
if(v[I][J] == 1 && !vis[I][J]) {
dfs(I, J);
grpId++;
ans++;
}
}
}
if(k == n-1) {
string str = "";
str += inttobin(ans, 15);
while(str.length()<100) str+="0";
return str;
}
// create string
vector< pair<int, int> > L; L.clear();
for(int I=2*n; I>=i; I--) L.push_back({I, j});
for(int J=j+1; J<=2*n; J++) L.push_back({i, J});
for(int I=0; I<=grpId; I++) freq[I] = -1;
stack<int> stk;
string refStr = "";
int Prev = 0;
int tmpid = 0;
for(auto c:L) {
if(Prev == 0 && v[c.first][c.second] == 1) {
if(freq[newGrpId[c.first][c.second]] == -1) {
stk.push(tmpid);
refStr += "1";
freq[newGrpId[c.first][c.second]] = tmpid;
ans--;
tmpid++;
} else {
stk.push(tmpid);
tmpid++;
refStr += "1";
while(stk.top() != freq[newGrpId[c.first][c.second]]) {
stk.pop();
refStr += "0";
}
}
}
Prev = v[c.first][c.second];
}
string str = "";
str += a[0][0][0];
str += inttobin(ans, 10);
str += refStr;
str += "1";
while(str.length() < 100) str += "0";
return str;
} else if(i == m || i == m-1) {
string str = "";
str += a[0][0][0];
str += a[2][0][0];
str += a[2][1][0];
str += a[2][2][0];
str += a[2][0].substr(1, k*3);
while(str.length() < 100) str += "0";
return str;
} else if(j == m || j == m-1) {
string str = "";
str += a[0][0][0];
str += a[0][2][0];
str += a[1][2][0];
str += a[2][2][0];
str += a[0][2].substr(1, k*3);
while(str.length() < 100) str += "0";
return str;
}
return a[0][0][0] + string(99, '0');
}
