#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
string sor(string s1, string s2) {
string s3;
s3.resize(100);
for(int i = 0; i < 100; i ++) {
if(s1[i]=='1'||s2[i]=='1') s3[i] = '1';
else s3[i] = '0';
}
return s3;
}
string shift(string s, int k) {
string s2;
s2.resize(100);
for(int i = 0; i+k<100;i++) {
s2[i+k] = s[i];
}
for(int i = 0; i < k; i++) s2[i] = '0';
return s2;
}
int A[50][50][50];
string process(vector<vector<string>> A, int a, int b, int k, int N) {
int i, j;
if(N<=4) {
if(k==0) {
for(i=0;i<3;i++) {
for(j=0;j<3;j++) {
A[i][j] = shift(A[i][j],(2*N+1)*(i+a)+(j+b));
//for(int m = 0; m < 9; m++) cout << A[i][j][m];
//cout << '\n';
}
}
}
string s3;
s3.resize(100);
for(int i = 0; i < 100; i++) s3[i] = '0';
for(i=0;i<3;i++) {
for(j=0;j<3;j++) s3 = sor(s3,A[i][j]);
}
/*cout <<a << ' ' << b << '\n';
for(i=0;i<2*N+1;i++) {
for(j=0;j<2*N+1;j++) cout << s3[(2*N+1)*i+j] << ' ';
cout << '\n';
}*/
if(k!=N-1) return s3;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
vector<vector<bool>> vis;
vis.resize(2*N+1);
for(i=0;i<2*N+1;i++) vis[i].resize(2*N+1);
for(i=0;i<2*N+1;i++) {
for(j=0;j<2*N+1;j++) vis[i][j] = false;
}
int ans = 0;
for(i=0;i<2*N+1;i++) {
for(j=0;j<2*N+1;j++) {
if(vis[i][j]) continue;
if(s3[(2*N+1)*i+j]=='1') {
ans++;
queue<int> Q;
Q.push((2*N+1)*i+j);
while(!Q.empty()) {
int c = Q.front();
Q.pop();
if(vis[c/(2*N+1)][c%(2*N+1)]) continue;
vis[c/(2*N+1)][c%(2*N+1)] = true;
for(int m = 0; m < 4; m++) {
int x = c/(2*N+1)+dx[m];
int y = c%(2*N+1)+dy[m];
if(0<=x&&x<2*N+1&&0<=y&&y<2*N+1) {
if(!vis[x][y]&&s3[(2*N+1)*x+y]=='1') {
Q.push((2*N+1)*x+y);
}
}
}
}
}
}
}
string ans_string;
ans_string.resize(100);
for(i=0;i<100;i++) ans_string[i] = '0';
int id = 0;
while(ans) {
ans_string[id] = (char)('0'+ans%2);
ans /= 2;
id++;
}
return ans_string;
}
else {
if(k==N-1) {
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
string s3;
s3.resize((2*N+1)*(2*N+1));
for(i=0;i<3;i++) {
for(j=0;j<3;j++) {
for(int m = 0; m < 81; m++) {
s3[(2*N+1)*((N-4)*i+m/9)+((N-4)*j+m%9)] = A[i][j][m];
}
}
}
/*for(i=0;i<3;i++) {
for(j=0;j<3;j++) {
for(int m = 0; m < 9; m++) {
for(int m2 = 0; m2 < 9; m2++) cout << A[i][j][9*m+m2] << ' ';
cout << '\n';
}
cout << "\n\n\n";
}
}*/
/*cout << N << '\n';
for(i=0;i<2*N+1;i++) {
for(j=0;j<2*N+1;j++) cout << s3[(2*N+1)*i+j] << ' ';
cout << '\n';
}*/
vector<vector<bool>> vis;
vis.resize(2*N+1);
for(i=0;i<2*N+1;i++) vis[i].resize(2*N+1);
for(i=0;i<2*N+1;i++) {
for(j=0;j<2*N+1;j++) vis[i][j] = false;
}
int ans = 0;
for(i=0;i<2*N+1;i++) {
for(j=0;j<2*N+1;j++) {
if(vis[i][j]) continue;
if(s3[(2*N+1)*i+j]=='1') {
ans++;
queue<int> Q;
Q.push((2*N+1)*i+j);
while(!Q.empty()) {
int c = Q.front();
Q.pop();
if(vis[c/(2*N+1)][c%(2*N+1)]) continue;
vis[c/(2*N+1)][c%(2*N+1)] = true;
for(int m = 0; m < 4; m++) {
int x = c/(2*N+1)+dx[m];
int y = c%(2*N+1)+dy[m];
if(0<=x&&x<2*N+1&&0<=y&&y<2*N+1) {
if(!vis[x][y]&&s3[(2*N+1)*x+y]=='1') {
Q.push((2*N+1)*x+y);
}
}
}
}
}
}
}
string ans_string;
ans_string.resize(100);
for(i=0;i<100;i++) ans_string[i] = '0';
int id = 0;
while(ans) {
ans_string[id] = (char)('0'+ans%2);
ans /= 2;
id++;
}
return ans_string;
}
if(k < 4) {
string s3;
s3.resize(100);
for(int i = 0; i < 100; i++) s3[i] = '0';
for(i=0;i<3;i++) {
for(j=0;j<3;j++) {
for(int m = 0; m < (2*k+1)*(2*k+1);m++) {
s3[(2*k+3)*(i+m/(2*k+1))+j+m%(2*k+1)] = A[i][j][m];
}
}
}
/*cout << a << ' ' << b << ' ' << k << '\n';
for(i=0;i<(2*k+3)*(2*k+3);i++) {
cout << s3[i] << ' ';
if(i%(2*k+3)==2*k+2) cout << '\n';
}
cout << '\n';*/
return s3;
}
else {
return A[a/(N-k-1)][b/(N-k-1)];
}
/*cout <<a << ' ' << b << '\n';
for(i=0;i<2*N+1;i++) {
for(j=0;j<2*N+1;j++) cout << s3[(2*N+1)*i+j] << ' ';
cout << '\n';
}*/
}
}
