#include <bits/stdc++.h>
using namespace std;
#include "mars.h"
#ifdef LOCAL
#include "grader.cpp"
#endif
const int MAXN=41;
int dsu[MAXN*MAXN];
int Findset(int i){
assert(dsu[i]!=i);
if(dsu[i]<0){
return i;
}
int root=Findset(dsu[i]);
dsu[i]=root;
return root;
}
void unite(int u,int v){
if(!dsu[u]||!dsu[v]){
return;
}
u=Findset(u),v=Findset(v);
if(u==v){
return;
}
if(dsu[u]<dsu[v]){
swap(u,v);
}
dsu[v]+=dsu[u],dsu[u]=v;
}
string process(vector<vector<string>> a,int stx,int sty,int k,int n){
int cc=0;
int grid[2*n+1][2*n+1];
memset(grid,0,sizeof(grid));
int sz=2*k+1;
string ans="";
for(int i=0;i<100;i++){
ans+="0";
}
if(stx||sty){
if(stx>sty){
for(int j=0;j<sz;j++){
grid[sz-1][j]=(a[0][0][j]-'0');
}
for(int sy=0;sy<3;sy++){
for(int j=0;j<sz;j++){
grid[sz+1][sy+j]=(a[2][sy][j]-'0');
}
}
int tim=0;
for(int j=0;j<sz+2;j++){
ans[tim]=(grid[sz+1][j]+'0');
tim++;
}
for(int j=0;j<sz;j++){
ans[tim]=(grid[sz-1][j]+'0');
tim++;
}
assert(tim<=100);
return ans;
}
else if(stx<sty){
for(int i=0;i<sz;i++){
grid[i][sz-1]=(a[0][0][i]-'0');
}
for(int sx=0;sx<3;sx++){
for(int i=0;i<sz;i++){
grid[sx+i][sz+1]=(a[sx][2][i]-'0');
}
}
int tim=0;
for(int i=0;i<sz+2;i++){
ans[tim]=(grid[i][sz+1]+'0');
tim++;
}
for(int i=0;i<sz;i++){
ans[tim]=(grid[i][sz-1]+'0');
tim++;
}
assert(tim<=100);
return ans;
}
else{
ans[0]=a[2][2][0],ans[1]=a[0][0][0];
return ans;
}
}
//cout << "PHASE " << k << endl;
memset(dsu,0,sizeof(dsu));
if(!k){
grid[0][0]=(a[0][0][0]-'0');
if(grid[0][0]){
dsu[1]=-1;
}
}
else{
int coef=sz-2,off=sz;
for(int sx=0;sx<3;sx++){
for(int sy=0;sy<3;sy++){
if(!sx&&!sy){
continue;
}
if(sx<sy){
for(int i=0;i<coef;i++){
grid[sx+i][sy+coef-1]=(a[sx][sy][off+i]-'0');
}
}
else if(sx>sy){
for(int j=0;j<coef;j++){
grid[sx+coef-1][sy+j]=(a[sx][sy][off+j]-'0');
}
}
else{
grid[sx+coef-1][sy+coef-1]=(a[sx][sy][1]-'0');
}
}
}
for(int i=0;i<=2*n;i++){
for(int j=0;j<=2*n;j++){
if(i==sz-1||j==sz-1){
continue;
}
grid[i][j]=0;
}
}
vector<pair<int,int>> v;
for(int j=0;j<sz;j++){
v.push_back({sz-1,j});
}
for(int i=sz-2;i>=0;i--){
v.push_back({i,sz-1});
}
stack<pair<int,int>> st;
int tim=0;
for(int l=0;l<v.size();l++){
int x=v[l].first,y=v[l].second;
if(!grid[x][y]){
continue;
}
//cout << "GOT " << x << ' ' << y << ' ' << tim << endl;
int r;
for(r=l;r<v.size();r++){
if(!grid[v[r].first][v[r].second]){
break;
}
}
r--;
dsu[x*MAXN+y+1]=-1;
for(int i=l+1;i<=r;i++){
int x2=v[i].first,y2=v[i].second;
dsu[x2*MAXN+y2+1]=-1;
//cout << "HERE " << x << ' ' << y << ' ' << x2 << ' ' << y2 << endl;
unite(x2*MAXN+y2+1,x*MAXN+y+1);
}
bool open=false,close=false;
if(a[0][0][tim]=='1'){
open=true;
}
tim++;
if(a[0][0][tim]=='1'){
close=true;
}
tim++;
if(close){
int x2=st.top().first,y2=st.top().second;
st.pop();
//cout << "HERE " << x << ' ' << y << ' ' << x2 << ' ' << y2 << endl;
unite(x2*MAXN+y2+1,x*MAXN+y+1);
}
if(open){
st.push({x,y});
}
l=r;
}
for(int i=tim;i<100;i++){
if(a[0][0][i]=='1'){
cc+=(1<<(i-tim));
}
}
}
for(int sx=0;sx<3;sx++){
for(int sy=0;sy<3;sy++){
if(!sx&&!sy){
continue;
}
if(sx<sy){
for(int i=0;i<sz;i++){
grid[sx+i][sy+sz-1]=(a[sx][sy][i]-'0');
}
}
else if(sx>sy){
for(int j=0;j<sz;j++){
grid[sx+sz-1][sy+j]=(a[sx][sy][j]-'0');
}
}
else{
grid[sx+sz-1][sy+sz-1]=(a[sx][sy][0]-'0');
}
}
}
// cout << "CHECK" << endl;
// for(int x=0;x<=2*n;x++){
// for(int y=0;y<=2*n;y++){
// cout << grid[x][y] << ' ';
// }
// cout << endl;
// }
for(int x=0;x<=2*n;x++){
for(int y=0;y<=2*n;y++){
if(x<sz&&y<sz){
continue;
}
if(grid[x][y]){
dsu[x*MAXN+y+1]=-1;
}
}
}
for(int x=0;x<=2*n;x++){
for(int y=0;y<=2*n;y++){
if(x<sz&&y<sz){
continue;
}
if(grid[x][y]){
int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
for(int bruh=0;bruh<4;bruh++){
int x2=x+dx[bruh],y2=y+dy[bruh];
if(x2<0||x2>2*n||y2<0||y2>2*n||!grid[x2][y2]){
continue;
}
unite(x2*MAXN+y2+1,x*MAXN+y+1);
}
}
}
}
for(int i=0;i<=2*n;i++){
for(int j=0;j<=2*n;j++){
if(grid[i][j]&&Findset(i*MAXN+j+1)==i*MAXN+j+1){
cc++;
}
}
}
if(k==n-1){
for(int i=0;i<30;i++){
if(cc&(1<<i)){
ans[i]='1';
}
}
return ans;
}
int tim=0;
vector<pair<int,int>> v;
for(int j=0;j<sz+2;j++){
v.push_back({sz+1,j});
}
for(int i=sz;i>=0;i--){
v.push_back({i,sz+1});
}
map<int,int> mp;
for(int l=0;l<v.size();l++){
int x=v[l].first,y=v[l].second;
if(!grid[x][y]){
continue;
}
int r;
for(r=l;r<v.size();r++){
if(!grid[v[r].first][v[r].second]){
break;
}
}
r--;
int root=Findset(x*MAXN+y+1);
if(mp.find(root)==mp.end()){
mp[root]=tim;
cc--;
}
else{
ans[mp[root]]='1';
ans[tim+1]='1';
}
mp[root]=tim;
tim+=2;
l=r;
}
assert(tim<=100);
for(int i=0;i<30;i++){
if(cc&(1<<i)){
assert(tim+i<100);
ans[tim+i]='1';
}
}
//cout << ans << endl;
return ans;
}
