#include<bits/stdc++.h>
#include"mars.h"
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;

#define x first
#define y second
#define mkp make_pair
#define pb push_back
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

string expand(string s){while(s.size()<100)s+='0';return s;}

string enc(vi o,int num){
	int siz=o.size();
	string res;
	For(i,0,siz-1){
		int j=i;
		if(!o[i])continue;
		while(j+1<siz&&o[i]==o[j+1])++j;
		bool l=0,r=0;
		Rep(k,i-1,0)l|=(o[k]==o[i]);
		For(k,j+1,siz-1)r|=(o[k]==o[i]);
		res+=(l+'0');
		res+=(r+'0');
		i=j;
	}
	res=expand(res);
	For(i,0,9)if(num>>i&1)res[i+90]='1';
	return res; 
}

vi dec(string s){
	vi res,stk; int c=0;
	for(int i=0;i<90;i+=2){
		bool l=(s[i]&1),r=(s[i+1]&1);
		if(!l&&!r)res.pb(++c);
		if(!l&&r)++c,res.pb(c),stk.pb(c);
		if(l&&!r)res.pb(stk.back()),stk.pop_back();
		if(l&r)res.pb(stk.back());
	}return res;
}

int n,mp[55][55],fa[55*55],allc;
inline int P(int x,int y){return x*(2*n+1)+y;}
inline int getf(int x){
	while(x!=fa[x])x=fa[x]=fa[fa[x]];
	return x;
}
inline void merge(int x,int y){x=getf(x),y=getf(y),fa[x]=y;}

bool vis[55*55];
int col[55][55];
int getcnt(int x){
	For(i,0,allc-1) vis[i]=0;
	For(i,0,2*n) For(j,0,2*n) if(i==x||j==x) vis[getf(P(i,j))]=1;
	int res=0;
	For(i,0,2*n) For(j,0,2*n) if(mp[i][j]&&getf(P(i,j))==P(i,j)&&!vis[P(i,j)]) ++res;
	return res;
}
int getres(){
	int res=0;
	For(i,0,2*n) For(j,0,2*n) if(mp[i][j]&&getf(P(i,j))==P(i,j)) ++res;
	return res;
}

string process(vector<vector<string> >a,int x,int y,int k,int N)
{
	memset(mp,0,sizeof mp);
	memset(fa,0,sizeof fa);
	memset(vis,0,sizeof vis);
	memset(col,0,sizeof col);
	
	n=N;
	if(x<2*(n-k-1) && y<2*(n-k-1)) return a[0][0];
	if(y!=2*(n-k-1)) {
		string res; res+=a[0][0][0];
		res+=a[1][0][0];
		For(i,0,2*k)res+=a[2][0][i];
		res+=a[0][1][0],res+=a[1][1][0];
		For(i,0,2*k)res+=a[2][1][i];
		return expand(res);
	}
	if(x!=2*(n-k-1)) {
		string res; res+=a[0][0][0];
		res+=a[0][1][0];
		For(i,0,2*k)res+=a[0][2][i];
		res+=a[1][0][0],res+=a[1][1][0];
		For(i,0,2*k)res+=a[1][2][i];
		return expand(res);
	}
	
//	cout<<x<<" "<<y<<" "<<k<<" "<<N<<endl;
//	For(i,0,2)For(j,0,2)cout<<a[i][j]<<"\n";puts("----");
	
	// clear:
	allc=(2*n+1)*(2*n+1);
	For(i,0,2*n)For(j,0,2*n)col[i][j]=mp[i][j]=0;
	For(i,0,allc-1)fa[i]=i;
	
	// k=0:
	if(k==0){
		For(i,0,2)For(j,0,2)mp[x+i][y+j]=a[i][j][0]&1;
		For(i,x,x+2)For(j,y,y+2)
			if(mp[i][j]){
				if(mp[i+1][j])merge(P(i,j),P(i+1,j));
				if(mp[i][j+1])merge(P(i,j),P(i,j+1));
			}
		if(x==0&&y==0){
			string res(100,'0'); int x=getres();
			For(i,0,9) res[i]='0'+(x>>i&1);
			return res;
		}
		vi tmp;
		Rep(i,2*k+4,0)tmp.pb(mp[x+i][y]*getf(P(x+i,y))); 
		For(i,1,2*k+4)tmp.pb(mp[x][y+i]*getf(P(x,y+i)));
		return enc(tmp,getcnt(x));
	}
	
	// getlst:
	vi lst=dec(a[2][2]);
	int lstres=0;
	For(i,0,9) if(a[2][2][i+90]&1) lstres|=(1<<i);
	
	// getmap:
	For(i,0,1)For(j,0,1)mp[x+i][y+j]=a[i][j][0]&1;
	For(i,0,2*k){
		For(j,0,1){
			mp[x+i+2][y+j]=a[2][j][i]&1;
			mp[x+j][y+i+2]=a[j][2][i]&1;
		}
		mp[x+i+2][y+2]=a[2][1][i+2*k+1]&1;
		mp[x+2][y+i+2]=a[1][2][i+2*k+1]&1;
	}
	
	// getlink:
	For(i,0,2*n)For(j,0,2*n)
		if(mp[i][j]){
			if(mp[i+1][j])merge(P(i,j),P(i+1,j));
			if(mp[i][j+1])merge(P(i,j),P(i,j+1));
		}
	vector<pii>p;
	Rep(i,2*k+2,0)p.pb(mkp(x+i+2,y+2));
	For(i,1,2*k+2)p.pb(mkp(x+2,y+i+2));
	int np=0,siz=p.size();
	For(i,0,siz-1){
		int j=i,x=p[i].x,y=p[i].y;
		if(!mp[x][y])continue;
		col[x][y]=lst[np];
		while(j+1<siz&&mp[p[j+1].x][p[j+1].y])
			++j,col[p[j].x][p[j].y]=lst[np];
		i=j;
		++np;
	}
	
//	cout<<"lst: "<<lstres<<endl;
//	For(i,0,2*n)For(j,0,2*n)cout<<mp[i][j]<<" \n"[j==2*n];
//	for(auto t:p)cout<<t.x<<" "<<t.y<<endl;
//	For(i,0,2*n)For(j,0,2*n)cout<<col[i][j]<<" \n"[j==2*n];
	
	For(i,0,siz-1){
		int c1=col[p[i].x][p[i].y];
		if(!c1)continue;
		For(j,i+1,siz-1){
			int c2=col[p[j].x][p[j].y];
			if(c1==c2)merge(P(p[i].x,p[i].y),P(p[j].x,p[j].y));
		}
	}
	
	if(!x&&!y){
//		For(i,0,2*n)For(j,0,2*n)cout<<getf(P(i,j))*mp[i][j]<<" \n"[j==2*n];
		string res(100,'0'); int x=getres()+lstres;
		For(i,0,9) res[i]='0'+(x>>i&1);
		return res;
	}
		
	vi tmp;
	Rep(i,2*k+4,0)tmp.pb(mp[x+i][y]*getf(P(x+i,y))); 
	For(i,1,2*k+4)tmp.pb(mp[x][y+i]*getf(P(x,y+i)));
	return enc(tmp,lstres+getcnt(x));
}