#include "mars.h"
#include<bits/stdc++.h>
using namespace std;
const bool DEBUG=0;
bool board[50][50];
int clr[50][50];
vector<pair<int,int>> adj[50][50];
int X,Y,N,dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
bool ok(int x,int y){
return (x>=X&&x<=2*N&&y>=Y&&y<=2*N);
}
void dfs(int x,int y,int pt){
clr[x][y]=pt;
if (DEBUG) cerr<<"dfs"<<x<<","<<y<<":"<<pt<<"\n";
for (int i=0;i<4;i++){
if (!ok(x+dx[i],y+dy[i])) continue;
if (clr[x+dx[i]][y+dy[i]]) continue;
if (!board[x+dx[i]][y+dy[i]]) continue;
dfs(x+dx[i],y+dy[i],pt);
}
for (auto i:adj[x][y]){
if (clr[i.first][i.second]) continue;
dfs(i.first,i.second,pt);
}
}
string process(vector <vector<string>> a, int x, int y, int k, int n)
{
string ret(100,'0');
bool lbord=(x==2*(n-k-1)),rbord=(y==2*(n-k-1));
memset(board,0,sizeof(board));
X=x; Y=y; N=n;
if (lbord&&rbord){
//corner cell
for (int i=0;i<=2;i++) for (int j=0;j<=2;j++) board[x+i][y+j]=a[i][j][0]=='1';
for (int i=0;i<=1;i++) for (int dy=0,j=y+2;j<=2*n;j++,dy++) board[x+i][j]=(a[i][2][dy]=='1');
for (int i=0;i<=1;i++) for (int dy=0,j=x+2;j<=2*n;j++,dy++) board[j][y+i]=(a[2][i][dy]=='1');
for (int dy=51,j=y+3;j<=2*n;j++,dy++) board[x+2][j]=(a[1][2][dy]=='1');
for (int dx=51,i=x+3;i<=2*n;i++,dx++) board[i][y+2]=(a[2][1][dx]=='1');
ret[0]=a[0][0][0];
vector<pair<int,int>> coord,stk;
coord.clear(); stk.clear();
for (int i=0;i<50;i++) for (int j=0;j<50;j++) adj[i][j].clear();
for (int i=2*n;i>=x+2;i--) if (board[i][y+2]&&!board[i+1][y+2]) coord.push_back({i,y+2});
for (int j=x+3;j<=2*n;j++) if (board[x+2][j]&&!board[x+2][j-1]) coord.push_back({x+2,j});
for (int i=11,dx=0;dx<coord.size();i+=2,dx++){
if (a[2][2][i]=='1'){
cerr<<stk.back().first<<","<<stk.back().second<<"<->"<<coord[dx].first<<","<<coord[dx].second<<"\n";
adj[stk.back().first][stk.back().second].push_back(coord[dx]);
adj[coord[dx].first][coord[dx].second].push_back(stk.back());
stk.pop_back();
}
if (a[2][2][i+1]=='1'){
stk.push_back(coord[dx]);
}
}
int pt=0,pt2=0,lpos[200],lval=0;
memset(clr,0,sizeof(clr)); memset(lpos,0,sizeof(lpos));
for (int i=2*n;i>=x;i--) for (int j=y;j<=2*n;j++){
if (clr[i][j]) continue;
if (!board[i][j]) continue;
++pt;
dfs(i,j,pt);
}
for (int i=2*n;i>=x;i--) if (board[i][y]&&!board[i+1][y]){
pt2++;
if (lpos[clr[i][y]]) ret[10+2*lpos[clr[i][y]]]='1',ret[10+2*pt2-1]='1';
lpos[clr[i][y]]=pt2;
}
for (int j=y+1;j<=2*n;j++) if (board[x][j]&&!board[x][j-1]){
pt2++;
if (lpos[clr[x][j]]) ret[10+2*lpos[clr[x][j]]]='1',ret[10+2*pt2-1]='1';
lpos[clr[x][j]]=pt2;
}
for (int i=1;i<=10;i++) lval+=(a[2][2][i]=='1')<<(i-1);
for (int i=1;i<=pt;i++) if ((!lpos[i])||(!x)) lval++;
for (int i=1;i<=10;i++) ret[i]='0'+((lval>>(i-1))&1);
if (!x){
for (int i=0;i<10;i++) ret[i]=ret[i+1];
for (int i=10;i<100;i++) ret[i]='0';
}
if (DEBUG){
cerr<<x<<" "<<y<<" at turn "<<k<<":"<<lval<<"\n";
for (int i=0;i<=2*n;i++){
for (int j=0;j<=2*n;j++) cerr<<board[i][j]<<" ";
cerr<<"\n";
}
for (int i=0;i<=2*n;i++){
for (int j=0;j<=2*n;j++) cerr<<clr[i][j]<<" ";
cerr<<"\n";
}
}
}else if (lbord){
ret[0]=a[0][0][0]; ret[1]=a[1][0][0];
for (int i=x+2;i<=2*n;i++) ret[i-x]=a[2][0][i-x-2];
if (y+1==2*(n-k-1)){
ret[51]=a[1][1][0];
for (int i=x+2;i<=2*n;i++) ret[i-x+50]=a[2][1][i-x-2];
}
}else if (rbord){
ret[0]=a[0][0][0]; ret[1]=a[0][1][0];
for (int j=y+2;j<=2*n;j++) ret[j-y]=a[0][2][j-y-2];
if (x+1==2*(n-k-1)){
ret[51]=a[1][1][0];
for (int j=y+2;j<=2*n;j++) ret[j-y+50]=a[1][2][j-y-2];
}
}else ret=a[0][0];
return ret;
}
/*
1
2
1 0 0 1 0
1 1 0 1 0
1 1 0 0 1
0 0 1 0 1
0 0 0 1 0
*/
