#include "mars.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define x real()
#define y imag()
#define point complex<int>
int to_id(int i, int j, int sz){
return i*sz + j;
}
int geometric(int n){
return (n*(n+1))/2;
}
int get_sz(int i, int j, int k, int n){
//cout<<"sz "<<i<<" "<<j<<" "<<k<<endl;
if(i< 2*(n-k-1) && j <2*(n-k-1)){
return 1;
}
if(k <0){
return 1;
}
if(i<2 && j<2){
return 1;
}
if(i == 0){
if(j%2 == 1){
return 1;
}
return geometric((2*n)+1 - j);
}
else if( j==0){
if(i%2 == 1){
return 1;
}
return geometric((2*n)+1-i);
}
else{
if(i>=j && i%2 == 1){
return 1;
}
if(j>=i && j%2 ==1){
return 1;
}
//cout<<(2*n)<<" "<<1-j<<endl;
//cout<<min((2*n)+1-j, (2*n)+1-i)<<endl;
return min((2*n)+1-j, (2*n)+1-i);
}
}
void append(vector<int>& v, vector<int>& b){
for(auto e: b){
v.push_back(e);
}
}
vector<int> to_vec(string s, int i, int j, int n, int k){
vector<int> res;
for(int l =0; l<get_sz(i, j,k,n); l++){
res.push_back(s[l]-'0');
}
return res;
}
string to_string(vector<int> v){
string res;
for(auto e:v){
res.push_back(e + '0');
}
while(res.size()<100){
res.push_back('0');
}
return res;
}
vector<vector<vector<int>>> a_to_vec(vector<vector<string>> a, int _i, int _j, int n, int k){
vector<vector<vector<int>>> res(3, vector<vector<int>>(3));
for(int i = 0;i<3; i++){
for(int j = 0; j<3; j++){
//cout<<"pos "<<i+_i<<" "<<j+_j<<endl;
//cout<<"n: "<<n<<endl;
//cout<<"sz: "<<get_sz(i+_i, j+_j, k, n)<<endl;
//cout<<a[i][j]<<endl;
res[i][j] = to_vec(a[i][j],i+_i,j+_j,n, k-1);
/*for(auto e: res[i][j]){
cout<<e<<" ";
}
cout<<endl;*/
}
}
return res;
}
vector<int> merge_left(vector<vector<vector<int>>>& a){
vector<int> res;
for(int i = 0; i<3; i++){
for(int j = 0; j<=i; j++){
append(res, a[i][j]);
}
}
return res;
}
vector<int> merge_right(vector<vector<vector<int>>>& a){
vector<int> res;
for(int i = 0; i<3; i++){
for(int j = i; j<3; j++){
//cout<<"inc "<<i<<" "<<j<<" "<<a[i][j].size()<<endl;
append(res, a[i][j]);
}
}
return res;
}
vector<int> merge_diag(vector<vector<vector<int>>>& a){
vector<int> res;
for(int i = 0; i<3; i++){
append(res, a[i][i]);
}
return res;
}
void dfs(vector<vector<char>>&r, point pos, vector<vector<bool>>& vis, int h){
vis[pos.x][pos.y] = true;
vector<point> d = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
for(auto e: d){
point np = pos + e;
if(np.x>=0 && np.x<h){
if(np.y>=0 && np.y<h){
if(!vis[np.x][np.y]){
if(r[np.x][np.y] == '1'){
dfs(r, np, vis, h);
}
}
}
}
}
}
int count_components(vector<vector<char>> r, int k){
int h = (2*k+3);
vector<vector<bool>> vis(h, vector<bool>(h));
int res= 0;
for(int i = 0; i<h; i++){
for(int j = 0; j<h; j++){
if(!vis[i][j]){
if(r[i][j] == '1'){
res++;
dfs(r, {i, j}, vis, h);
}
}
}
}
return res;
}
string to_str(int v){
string res(100, '0');
for(int i = 0; i<20; i++){
if(v & (1<<i)){
res[i] = '1';
}
}
return res;
}
vector<int> process_edge(vector<vector<vector<int>>> a, int i, int j, int k){
if(j==0){
return merge_left(a);
}
else{
if(i==0){
return merge_right(a);
}
else{
return merge_diag(a);
}
}
}
vector<vector<vector<int>>> simulate(int n){
int sz = 2*n+1;
vector<vector<vector<int>>> content(sz, vector<vector<int>>(sz));
for(int i = 0; i<sz; i++){
for(int j = 0; j<sz; j++){
content[i][j].push_back(i*sz + j);
//cout<<i<<" "<<j<<" "<<i*sz+j<<endl;
}
}
for(int k = 0; k<n-1; k++){
for(int i = 0; i<=2*(n-k-1); i++){
for(int j = 0; j<=2*(n-k-1); j++){
if(i == 2*(n-k-1) || j == 2*(n-k-1)){
vector<vector<vector<int>>>a (3, vector<vector<int>>(3));
for(int h= 0; h<3; h++){
for(int l = 0; l<3; l++){
a[h][l] = content[i+h][j+l];
}
}
content[i][j]= process_edge(a, i, j, k);
}
}
}
}
return content;
}
vector<vector<char>> get_final(vector<vector<vector<int>>> a, int n){
vector<vector<vector<int>>> final_pos = simulate(n);
vector<vector<char>> m(2*n+1, vector<char>(2*n+1, '0'));
int sz = 2*n+1;
for(int i = 0; i<3; i++){
for(int j = 0; j<3; j++){
if(final_pos[i][j].size() != a[i][j].size()){
//cout<<"error "<<i<<" "<<j<<" "<<final_pos[i][j].size()<<" "<<a[i][j].size()<<endl;
}
for(int k = 0;k<final_pos[i][j].size(); k++){
auto e = final_pos[i][j][k];
m[e/sz][e%sz] = a[i][j][k] + '0';
}
}
}
return m;
}
std::string process(std::vector <std::vector<std::string>> a, int i, int j, int k, int n)
{
/*simulate(n);
return string(101, '0');*/
if(k ==n-1){
return to_str(count_components(get_final(a_to_vec(a, i, j, n, k), n), k));
}
else{
if(i == 2*(n-k-1) || j == 2*(n-k-1)){
vector<int> res =process_edge(a_to_vec(a, i, j, n, k), i, j, k);
return to_string(res);
}
else{
return a[0][0];
}
}
}
