#include <bits/stdc++.h>
using namespace std;

#include "mars.h"


const int dy[4] = {-1,0,1,0};
const int dx[4] = {0,1,0,-1};

void dfs(vector<vector<bool>>& grid, vector<vector<bool>>& visited, int i, int j, int n, int m){
    visited[i][j] = 1;
    for(int k=0; k<4; k++){
        int newi=i+dy[k], newj=j+dx[k];
        if(newi >= 0 && newj >= 0 && newi <n && newj <m && !visited[newi][newj] && grid[newi][newj]){
            dfs(grid, visited, newi, newj, n, m);
        }
    }


}
// subtask 2 - string to store the state of island, last bit to represent visited
// last phase process and return binary
std::string process(std::vector <std::vector<std::string>> a, int I, int J, int K, int n)
{
    string ans(100,'0');
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            if(a[i][j][99] == '1'){
                // visited before
                for(int k=0; k<100; k++){
                    ans[k] |= a[i][j][k];
                }
            } else{
                // not visited
                ans[(I+i)*(2*n+1)+(J+j)] |= a[i][j][0];
            // cerr << i << " " << j << " " << " " << i*(2*n+1)+j << " " << a[i][j][0] << endl;
            }
        }
    }
    ans[99] = '1';

    if(K != n-1)return ans;



    vector<vector<bool>> grid(2*n+1, vector<bool>(2*n+1));
    vector<vector<bool>> visited(2*n+1, vector<bool>(2*n+1));
    int cnt = 0;
    for(int i=0; i<(2*n+1); i++){
        for(int j=0; j<(2*n+1); j++){
            grid[i][j] = (ans[i*(2*n+1)+j]=='1');
        }
    }
    for(int i=0; i<(2*n+1); i++){
        for(int j=0; j<(2*n+1); j++){
            if(grid[i][j] && !visited[i][j]){
                cnt++;
                dfs(grid,visited,i,j,2*n+1,2*n+1);
            }
        }
    }

    string fans(100,'0');


    for(int i=0; i<=log2(cnt); i++){
        if((cnt >> i)&1){
            fans[i] = '1';
        }
    }
    // cerr << cnt << " "<< fans;
    return fans;


}


/*
  for each string, if visited - then set the res i-j to it
  set to visited
  return

  string storing
  0 indexed
  i j = i*(2n+1) + j

  
*/