#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
string process (vector <vector <string> > a, int i, int j, int k, int n) {
n = 2*n+1;
if (n == 3) {
vector <vector <char> > mat(n, vector <char> (n, false));
for (ll ii = 0; ii < 3; ii++) {
for (ll jj = 0; jj < 3; jj++) {
mat[ii][jj] = a[ii][jj][0];
}
}
vector <vector <char> > vis(n, vector <char> (n, false));
ll ans = 0;
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
if (mat[i][j] == '0') continue;
if (vis[i][j]) continue;
ans++;
queue <ll> q;
q.push(i);
q.push(j);
while (q.size()) {
ll i = q.front(); q.pop();
ll j = q.front(); q.pop();
if (mat[i][j] == '0') continue;
if (vis[i][j]) continue;
vis[i][j] = true;
if (0 < i) {
q.push(i-1);
q.push(j);
}
if (i < n-1) {
q.push(i+1);
q.push(j);
}
if (0 < j) {
q.push(i);
q.push(j-1);
}
if (j < n-1) {
q.push(i);
q.push(j+1);
}
}
}
}
string sans(100, '0');
for (ll i = 0; i < 10; i++) {
sans[i] = (ans>>i&1 ? '1' : '0');
}
return sans;
}
vector <vector <bitset <100> > > aa(3, vector <bitset <100> > (3, bitset <100> (0)));
if (k == 0) {
for (ll ii = i; ii < i+3; ii++) {
for (ll jj = j; jj < j+3; jj++) {
swap(a[ii-i][jj-j][0], a[ii-i][jj-j][(ii/2)*((n+1)/2)+(jj/2)]);
}
}
}
for (ll i = 0; i < 3; i++) {
for (ll j = 0; j < 3; j++) {
for (ll k = 0; k < 100; k++) {
aa[i][j][k] = a[i][j][k] == '1';
}
}
}
aa[0][0] |= aa[0][2];
aa[0][0] |= aa[2][0];
aa[0][0] |= aa[2][2];
aa[0][1] |= aa[2][1];
aa[1][0] |= aa[1][2];
if (k+1 != n/2) {
string ans = "";
for (ll k = 0; k < 100; k++) ans += char('0'+aa[0][0][k]);
return ans;
}
// final phase
vector <vector <char> > mat(n, vector <char> (n, '*'));
for (ll sti = 0; sti < 2; sti++) {
for (ll stj = 0; stj < 2; stj++) {
for (ll i = sti; i < n; i += 2) {
for (ll j = stj; j < n; j += 2) {
ll pos = (i/2)*((n+1)/2)+(j/2);
mat[i][j] = '0'+aa[sti][stj][pos];
}
}
}}
vector <vector <char> > vis(n, vector <char> (n, false));
ll ans = 0;
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
if (mat[i][j] == '0') continue;
if (vis[i][j]) continue;
ans++;
queue <ll> q;
q.push(i);
q.push(j);
while (q.size()) {
ll i = q.front(); q.pop();
ll j = q.front(); q.pop();
if (mat[i][j] == '0') continue;
if (vis[i][j]) continue;
vis[i][j] = true;
if (0 < i) {
q.push(i-1);
q.push(j);
}
if (i < n-1) {
q.push(i+1);
q.push(j);
}
if (0 < j) {
q.push(i);
q.push(j-1);
}
if (j < n-1) {
q.push(i);
q.push(j+1);
}
}
}
}
string sans(100, '0');
for (ll i = 0; i < 10; i++) {
sans[i] = (ans>>i&1 ? '1' : '0');
}
return sans;
}
