#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'
//#define int long long
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
const int dx[]={-1, 1, 0, 0, 0};
const int dy[]={0, 0, 1, -1, 0};
typedef long long ll;
using namespace std;
const int mx=50+12;
const int mod=998244353;
const bool T=1;
int used[mx][mx];
int was[mx][mx];
int lx[mx][mx][mx], rx[mx][mx][mx];
int ly[mx][mx][mx], ry[mx][mx][mx];
int pos(int x,int y,int n){
return x*n+y;
}
void dfs(int x,int y,int n){
used[x][y]=1;
for(int i=0;i<4;i++){
int x1=dx[i]+x, y1=dy[i]+y;
if(min(x1, y1)>=0 && max(x1, y1)<n && !used[x1][y1]){
dfs(x1, y1, n);
}
}
}
void init(int n){
for(int i=0;i<2*n+1;i++){
for(int j=0;j<2*n+1;j++){
for(int k=0;k<=n;k++){
lx[i][j][k]=rx[i][j][k]=-1;
ly[i][j][k]=ry[i][j][k]=-1;
if(k<=4){
lx[i][j][k]=i, rx[i][j][k]=i+2*k;
ly[i][j][k]=j, ry[i][j][k]=j+2*k;
}
}
}
}
for(int k=n;k>5;k--){
for(int i=0;i+2*k<2*n+1;i++){
for(int j=0;j+2*k<2*n+1;j++){
lx[i][j][k-1]=i, ly[i][j][k-1]=j;
rx[i][j][k-1]=i+9, ry[i][j][k-1]=j+9;
}
}
for(int i=0;i+2*k-2<2*n+1;i++){
for(int j=0;j+2*k-2<2*n+1;j++){
if(lx[i][j][k-1]==-1){
if(max(i, j)+2*k-2 == 2*n+1){
if(i>j){
rx[i][j][k-1]=i+2*(k-1), ry[i][j][k-1]=j+9;
lx[i][j][k-1]=rx[i][j][k-1]-9, ly[i][j][k-1]=ry[i][j][k-1]-9;
}
else if(i<j){
rx[i][j][k-1]=i+9, ry[i][j][k-1]=j+2*(k-1);
lx[i][j][k-1]=rx[i][j][k-1]-9, ly[i][j][k-1]=ry[i][j][k-1]-9;
}
else{
rx[i][j][k-1]=i+2*(k-1), ry[i][j][k-1]=j+2*(k-1);
lx[i][j][k-1]=rx[i][j][k-1]-9, ly[i][j][k-1]=ry[i][j][k-1]-9;
}
}
else{
if(i<j){
rx[i][j][k-1]=i+9, ry[i][j][k-1]=(j*2+2*(k-1))/2+5;
lx[i][j][k-1]=rx[i][j][k-1]-9, ly[i][j][k-1]=ry[i][j][k-1]-9;
}
else if(i==j){
rx[i][j][k-1]=(i*2+2*(k-1))/2+5, ry[i][j][k-1]=(j*2+2*(k-1))/2+5;
lx[i][j][k-1]=rx[i][j][k-1]-9, ly[i][j][k-1]=ry[i][j][k-1]-9;
}
else{
rx[i][j][k-1]=(i*2+2*(k-1))/2+5, ry[i][j][k-1]=j+9;
lx[i][j][k-1]=rx[i][j][k-1]-9, ly[i][j][k-1]=ry[i][j][k-1]-9;
}
}
}
}
}
}
}
void upd(string a, int x,int y, int k){
if(lx[x][y][k]==-1){
return;
}
int pos=0;
for(int i=lx[x][y][k];i<=rx[x][y][k];i++){
for(int j=ly[x][y][k];j<=ry[x][y][k];j++){
used[i][j]=(a[pos] == '1');
was[i][j]=1;
pos++;
}
}
}
std::string process(std::vector<std::vector<std::string> > a,int x,int y,int k,int n){
init(n);
k++;
string ans="";
while(ans.size()<100){
ans+='0';
}
for(int i=x;i<x+2*k+1;i++){
for(int j=y;j<y+2*k+1;j++){
was[i][j]=0;
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
upd(a[i][j], x+i, y+j, k-1);
}
}
for(int i=x;i<x+2*k+1;i++){
for(int j=y;j<y+2*k+1;j++){
if(!was[i][j]){
cout<<"! "<<x<<' '<<y<<' '<<k<<ent;
cout<<"FIND "<<i<<' '<<j<<ent;
assert(0);
}
}
}
if(lx[x][y][k]!=-1){
int pos=0;
for(int i=lx[x][y][k];i<=rx[x][y][k];i++){
for(int j=ly[x][y][k];j<=ry[x][y][k];j++){
ans[pos]=used[i][j]+'0';
pos++;
}
}
}
if(n==k){
for(int i=0;i<2*n+1;i++){
for(int j=0;j<2*n+1;j++){
used[i][j]=1-used[i][j];
}
}
int cnt=0;
for(int i=0;i<2*n+1;i++){
for(int j=0;j<2*n+1;j++){
if(!used[i][j]){
cnt++;
dfs(i, j, 2*n+1);
}
}
}
for(int i=0;i<100;i++){
if(i>=20){
ans[i]='0';
}
else{
if((cnt&(1<<i))){
ans[i]='1';
}
else{
ans[i]='0';
}
}
}
return ans;
}
return ans;
}
