#include<bits/stdc++.h>
#include"mars.h"
using namespace std;
int const N=2333,dx[]={-1,0,0,1},dy[]={0,-1,1,0};
int f[N];
int find(int x){
return f[x]^x?f[x]=find(f[x]):x;
}
void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx^fy)f[fx]=fy;
}
int ord(int x,int y,int n){
return x*n+y;
}
string solve(vector<vector<string>>const&a,int n){
string s=string(N,48);
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
for(int x=0;x<n/2;x++)
for(int y=0;y<n/2;y++)
s[ord(i+x*2,j+y*2,n)]=a[i][j][ord(x,y,n/2)];
//rebuild the whole graph
for(int i=0;i<n*n;i++)
if(s[i]==49)f[i]=i;
for(int x=0;x<n;x++)
for(int y=0;y<n;y++)
for(int i=0;i<4;i++){
int tx=x+dx[i],ty=y+dy[i],p1=ord(x,y,n),p2=ord(tx,ty,n);
if(tx<0||tx>=n||ty<0||ty>=n||s[p1]==48||s[p2]==48)continue;
merge(p1,p2);
}
int cnt=0;
for(int i=0;i<n*n;i++)
cnt+=s[i]==49&&find(i)==i;
//use dsu to count the answer
string res=string(100,48);
for(int i=0;cnt;i++)
res[i]+=cnt&1,cnt>>=1;
return res;
}
string process(vector<vector<string>>a,int ti,int tj,int k,int n){
string s=string(100,48);
if(k==n-1)
return solve(a,2*n+1);
for(int i=0;i<3;i+=2)
for(int j=0;j<3;j+=2)
for(int x=0;x<=k;x++)
for(int y=0;y<=k;y++)
s[ord(x+i/2,y+j/2,k+2)]=a[i][j][ord(x,y,k+1)];
//(x,y) stores the info of (x+2i,y+2j) instead of (x+i,y+j) (i,j\in N)
return s;
}
