#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define INF (int)(1e9+1)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
//at phase 4 we make everything a map of 10x10
//phase 5 shift diagonal
//phase 6
//phase 7
//phase 8
//phase 9
//phase 10
int iii;
string process(vector <vector<string>> a, int I, int J, int k, int n)
{
iii=J;
string ans(100,'0');
if(k!=n-1){
if(k<4){ //make 10 x 10
int s = 2*k+1;
int f = 2*k+3;
vii g(40,vector<int>(40));
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
for(int k=0;k<s*s;k++){
g[k/s+i][k%s+j] = a[i][j][k] - '0';
}
}
}
for(int k=0;k<f*f;k++)ans[k] = '0' + g[k/f][k%f];
}else{
ans = a[0][0];
if(!I && !J)ans = a[0][0];
else if(I==J){
if(k>=7 && I==1)ans = a[0][0];
else ans = a[2][2];
}
else if(!I){
if(k>=7 && J==1)ans = a[0][0];
else ans = a[0][2];
}
else if(!J){
if(k>=7 && I==1)ans = a[0][0];
else ans = a[2][0];
}
else if(n==10){
if(I==7 && J==5)ans = a[2][2];
if(I==5 && J==3)ans = a[2][2];
if(I==4 && J==3)ans = a[1][0];
if(I==2 && J==1)ans = a[2][1];
if(I==5 && J==7)ans = a[2][2];
if(I==3 && J==5)ans = a[2][2];
if(I==3 && J==4)ans = a[1][0];
if(I==1 && J==2)ans = a[1][2];
}
}
}
if(k == n-1){
vii g(40,vector<int>(40,0));
if(n<=5){
int s = 2*n-1;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
for(int k=0;k<s*s;k++){
g[k/s+i][k%s+j] = a[i][j][k] - '0';
}
}
}
}
else if(n<=8){
int s = 9;
int sh = (n-5)*2;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
for(int k=0;k<s*s;k++){
int ii = i+sh;
int jj = j+sh;
if(!i && !j)g[k/s][k%s] = a[i][j][k] - '0';
else if(i==j)g[k/s + ii][k%s + jj] = a[i][j][k] - '0';
else if(!i)g[k/s][k%s + jj] = a[i][j][k] - '0';
else if(!j)g[k/s + ii][k%s] = a[i][j][k] - '0';
else if(n==10){
}
}
}
}
}
else if(n<=10){
int s = 9;
int sh = (n-5)*2;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
for(int k=0;k<s*s;k++){
int ii = i+sh;
int jj = j+sh;
if(!i && !j)g[k/s][k%s] = a[i][j][k] - '0';
else if(i==j){
if(i==2)g[k/s + ii][k%s + jj] = a[i][j][k] - '0';
if(i==1)g[k/s + ii-4][k%s + jj-4] = a[i][j][k] - '0';
}
else if(!i){
if(j==2)g[k/s][k%s + jj] = a[i][j][k] - '0';
if(j==1)g[k/s][k%s + jj-4] = a[i][j][k] - '0';
}
else if(!j){
if(i==2)g[k/s + ii][k%s] = a[i][j][k] - '0';
if(i==1)g[k/s + ii-4][k%s] = a[i][j][k] - '0';
}else if(j==1){
g[k/s+11][k%s+9] = a[i][j][k] - '0';
}else if(i==1){
g[k/s+9][k%s+11] = a[i][j][k] - '0';
}
}
}
}
}
n = 2*n+1;
bool debug = 0;
if(debug){
cout<<'\n';
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<g[i][j]<<" ";
}
cout<<'\n';
}
}
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int res = 0;
vector<vector<bool>>vis(n,vector<bool>(n,0));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(!vis[i][j] && g[i][j]){
queue<pii>q;
q.push({i,j});
while(!q.empty()){
int x = q.front().fi;
int y = q.front().se;
vis[x][y] = 1;
q.pop();
//cout<<x<<" "<<y<<'\n';
for(int k=0;k<4;k++){
int xn = x+dx[k];
int yn = y+dy[k];
if(xn>=0 && yn>=0 && xn<n && yn<n && g[xn][yn] && !vis[xn][yn]){
q.push({xn,yn});
vis[xn][yn] = 1;
}
}
}
res++;
}
}
}
for(int i=0;i<30;i++)if(res&(1<<i))ans[i] = '1';
}
return ans;
}
