#include "mars.h"
#include<bits/stdc++.h>
using namespace std;
int g(int i,int j,int n){
return i*(2*n+1)+j;
}
int p[1000005];
int fp(int a){
if(a==p[a])return a;
return p[a]=fp(p[a]);
}
void un(int a,int b){
p[fp(b)]=fp(a);
}
std::string process(std::vector <std::vector<std::string>> a, int i, int j, int k, int n)
{
string ans(100,'0');
ans=a[0][0];
if(k==0){
ans[0]='0';
for(int ii=0;ii<=2;ii++)for(int jj=0;jj<=2;jj++){
if(a[ii][jj][0]=='1'){
//cerr<<"do:"<<i+ii<<" "<<j+jj<<"\n";
ans[g(i+ii,j+jj,n)]='1';
}
}
/*cerr<<"ans:\n";
cerr<<"i,j:"<<i<<' '<<j<<"\n";
for(int i=0;i<2*n+1;i++){
for(int j=0;j<2*n+1;j++){
cerr<<ans[g(i,j,n)]<<' ';
}
cerr<<"\n";
}*/
}else{
//cerr<<"work\n";
ans=a[0][0];
for(int ii=0;ii<=2;ii++)for(int jj=0;jj<=2;jj++)for(int k=0;k<100;k++){
if(a[ii][jj][k]=='1')ans[k]='1';
}
//cerr<<"work\n";
}
if(k==n-1){
/*cerr<<"LAST:\n";
cerr<<"i,j:"<<i<<' '<<j<<"\n";
for(int i=0;i<2*n+1;i++){
for(int j=0;j<2*n+1;j++){
cerr<<ans[g(i,j,n)]<<' ';
}
cerr<<"\n";
}
cerr<<"max:"<<(2*n+1)*(2*n+1)<<"\n";*/
for(int i=0;i<100;i++)p[i]=i;
for(int i=0;i<2*n+1;i++)for(int j=0;j<2*n+1;j++){
if(i!=2*n){
if(ans[g(i,j,n)]=='1'&&ans[g(i+1,j,n)]=='1')un(g(i,j,n),g(i+1,j,n));
}
if(j!=2*n){
if(ans[g(i,j,n)]=='1'&&ans[g(i,j+1,n)]=='1')un(g(i,j,n),g(i,j+1,n));
}
}
int rans=0;
for(int i=0;i<2*n+1;i++)for(int j=0;j<2*n+1;j++){
if(ans[g(i,j,n)]=='1'){
if(fp(g(i,j,n))==g(i,j,n))rans++;
}
}
//cerr<<rans<<"\n";
ans=string(100,'0');
for(int i=0;i<30;i++){
if((rans>>i)&1)ans[i]='1';
}
}
//cerr<<"i,j:"<<i<<' '<<j<<"\n";
/*for(int i=0;i<2*n+1;i++){
for(int j=0;j<2*n+1;j++){
cerr<<ans[g(i,j,n)]<<' ';
}
cerr<<"\n";
}*/
//cerr<<ans<<"\n";
return ans;
}
/*
1
4
1 1 0 1 1 1 1 0 1
1 1 0 0 0 1 1 0 0
1 0 1 1 1 1 0 1 1
0 1 0 0 0 1 0 1 1
0 1 1 1 1 1 0 1 1
1 1 0 0 0 1 1 0 0
1 0 1 1 1 1 1 0 0
0 1 0 0 0 1 1 0 0
0 1 1 1 1 1 1 0 0
*/
