#include "mars.h"
#include<vector>
#include<string>
#include<queue>
#include<iostream>
#include<cstdio>
using namespace std;
inline void subf(int y,int x,char a,int n,vector<vector<int>>& m) {
if(0 <= y && y <= n && 0 <= x && x <= n)m[y][x] = (a=='0'?0:1);
}
int par(int x,vector<int>& p) {
if(p[x] == x)return x;
else return p[x] = par(p[x],p);
}
string solve(vector<vector<int>>& m,int n) {
string res = string(100 ,'0');
int C = n*n;
vector<int> p(C);
for(int ii=0;ii<C;ii++)p[ii] = ii;
for(int y=1;y<n;y++)for(int x=0;x<n;x++) {
if(m[y][x] && m[y-1][x]) {
p[par(y*n+x,p)] = par((y-1)*n+x,p);
}
}
for(int y=0;y<n;y++)for(int x=1;x<n;x++) {
if(m[y][x] && m[y][x-1]) {
p[par(y*n+x,p)] = par(y*n+x-1,p);
}
}
vector<int> cnt(C,0);
for(int y=0;y<n;y++)for(int x=0;x<n;x++)if(m[y][x])cnt[par(y*n+x,p)]++;
int ans = 0;
for(int ii=0;ii<C;ii++)if(cnt[ii])ans++;
queue<int> resq;
while(ans) {
resq.push(ans&1);
ans /= 2;
}
for(int ii=0;!resq.empty();ii++) {
res[ii] = '0'+resq.front();
resq.pop();
}
return res;
}
std::string process(std::vector <std::vector<std::string>> a, int i, int j, int k, int n)
{
int s = 2*n+1;
string res = string(100 ,'0');
if(n == 1) {
vector<vector<int>> m(3,vector<int>(3));
for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y][x] = (a[y][x][0] == '0'?0:1);
res = solve(m,3);
}
else if(k == 0) {
for(int ii=0;ii<3;ii++)for(int jj=0;jj<3;jj++)res[ii*3+jj] = a[ii][jj][0];
}
else if(n == 2) {
vector<vector<int>> m(5,vector<int>(5));
for(int y=0;y<2;y++)for(int x=0;x<2;x++)m[y][x] = (a[0][0][y*3+x] == '0'?0:1);
for(int y=0;y<2;y++)for(int x=0;x<3;x++)m[y][2+x] = (a[0][2][y*3+x] == '0'?0:1);
for(int y=0;y<3;y++)for(int x=0;x<2;x++)m[2+y][x] = (a[2][0][y*3+x] == '0'?0:1);
for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[2+y][2+x] = (a[2][2][y*3+x] == '0'?0:1);
res = solve(m,5);
}
else if(n == 3) {
if(k == 1) {
if(i < 2 && j == 2)res = a[0][2];
else if(i == 2 && j < 2)res = a[2][0];
else if(i == 2 && j == 2)res = a[2][2];
else res = a[0][0];
}
else {
vector<vector<int>> m(7,vector<int>(7));
for(int y=0;y<1;y++)for(int x=0;x<1;x++)m[y][x] = (a[0][0][y*3+x] == '0'?0:1);
for(int y=0;y<1;y++)for(int x=0;x<3;x++)m[y][x+1] = (a[0][1][y*3+x] == '0'?0:1);
for(int y=0;y<1;y++)for(int x=0;x<3;x++)m[y][x+4] = (a[0][2][y*3+x] == '0'?0:1);
for(int y=0;y<3;y++)for(int x=0;x<1;x++)m[y+1][x] = (a[1][0][y*3+x] == '0'?0:1);
for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+1][x+1] = (a[1][1][y*3+x] == '0'?0:1);
for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+1][x+4] = (a[1][2][y*3+x] == '0'?0:1);
for(int y=0;y<3;y++)for(int x=0;x<1;x++)m[y+4][x] = (a[2][0][y*3+x] == '0'?0:1);
for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+4][x+1] = (a[2][1][y*3+x] == '0'?0:1);
for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+4][x+4] = (a[2][2][y*3+x] == '0'?0:1);
res = solve(m,7);
}
}
else if(k == 1) {
int y = -1,x = -1;
if(i < s%9) {
if(i == 0)y = 0;
else if(i == 2)y = 1;
else if(i == 4)y = 2;
}
else {
if((s-i)%9 == 0)y = 0;
else if((s-i)%9 == 7)y = 1;
else if((s-i)%9 == 5)y = 2;
}
if(j < s%9) {
if(j == 0)x = 0;
else if(j == 2)x = 1;
else if(j == 4)x = 2;
}
else {
if((s-j)%9 == 0)x = 0;
else if((s-j)%9 == 7)x = 1;
else if((s-j)%9 == 5)x = 2;
}
if(y >= 0 && x >= 0)res = a[y][x];
}
else if(k == 2) {
int y = -1,x = -1;
if(i < s%9) {
if(i == 0)y = 0;
else if(i == 1)y = 1;
else if(i == 2)y = 2;
}
else {
if((s-i)%9 == 0)y = 0;
else if((s-i)%9 == 8)y = 1;
else if((s-i)%9 == 7)y = 2;
}
if(j < s%9) {
if(j == 0)x = 0;
else if(j == 1)x = 1;
else if(j == 2)x = 2;
}
else {
if((s-j)%9 == 0)x = 0;
else if((s-j)%9 == 8)x = 1;
else if((s-j)%9 == 7)x = 2;
}
if(y >= 0 && x >= 0)res = a[y][x];
}
else if(n == 4) {
vector<vector<int>> m(9,vector<int>(9));
for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y][x] = (a[0][0][y*3+x] == '0'?0:1);
for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y][x+3] = (a[0][1][y*3+x] == '0'?0:1);
for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y][x+6] = (a[0][2][y*3+x] == '0'?0:1);
for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+3][x] = (a[1][0][y*3+x] == '0'?0:1);
for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+3][x+3] = (a[1][1][y*3+x] == '0'?0:1);
for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+3][x+6] = (a[1][2][y*3+x] == '0'?0:1);
for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+6][x] = (a[2][0][y*3+x] == '0'?0:1);
for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+6][x+3] = (a[2][1][y*3+x] == '0'?0:1);
for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+6][x+6] = (a[2][2][y*3+x] == '0'?0:1);
res = solve(m,9);
}
else if(k == 3) {
for(int ii=0;ii<3;ii++)for(int jj=0;jj<3;jj++)for(int kk=0;kk<3;kk++)for(int ll=0;ll<3;ll++) {
res[ii*27+jj*9+kk*3+ll] = a[ii][kk][jj*3+ll];
}
}
else if(n == 5) {
vector<vector<int>> m(11,vector<int>(11));
for(int y=0;y<2;y++)for(int x=0;x<2;x++)m[y][x] = (a[0][0][y*9+x] == '0'?0:1);
for(int y=0;y<2;y++)for(int x=0;x<9;x++)m[y][x+2] = (a[0][2][y*9+x] == '0'?0:1);
for(int y=0;y<9;y++)for(int x=0;x<2;x++)m[y+2][x] = (a[2][0][y*9+x] == '0'?0:1);
for(int y=0;y<9;y++)for(int x=0;x<9;x++)m[y+2][x+2] = (a[2][2][y*9+x] == '0'?0:1);
res = solve(m,11);
}
else if(n < 9 && k == n-1) {
vector<vector<int>> m(n+n+1,vector<int>(n+n+1));
for(int y=0;y<n+n-8;y++)for(int x=0;x<n+n-8;x++)m[y][x] = (a[0][0][y*9+x] == '0'?0:1);
for(int y=0;y<n+n-8;y++)for(int x=0;x<9;x++)m[y][x+n+n-8] = (a[0][2][y*9+x] == '0'?0:1);
for(int y=0;y<9;y++)for(int x=0;x<n+n-8;x++)m[y+n+n-8][x] = (a[2][0][y*9+x] == '0'?0:1);
for(int y=0;y<9;y++)for(int x=0;x<9;x++)m[y+n+n-8][x+n+n-8] = (a[2][2][y*9+x] == '0'?0:1);
res = solve(m,n+n+1);
}
else if((k*2+s%9-1)/8*9 < 2*n+1) {
int c = (k*2+s%9-1)/8,y = 0,x = 0;
if(i == c) {
if((k*2+s%9+1)/8 > c && (s%9-1)%2 > 0)y = 1;
else y = 2;
}
if(j == c) {
if((k*2+s%9+1)/8 > c && (s%9-1)%2 > 0)x = 1;
else x = 2;
}
if(i > c)y = 2;
if(j > c)x = 2;
res = a[y][x];
}
else if(k < n-1) {
if(i == 0 && j == 0) {
vector<vector<int>> m(n+1,vector<int>(n+1));
for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<s%9;jj++)m[ii][jj] = (a[0][0][ii*9+jj]=='0'?0:1);
for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)if(s%9+jj <= n)m[ii][s%9+jj] = (a[0][1][ii*9+jj]=='0'?0:1);
for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)if(s%9+9+jj <= n)m[ii][s%9+9+jj] = (a[0][2][ii*9+jj]=='0'?0:1);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)if(s%9+ii <= n)m[s%9+ii][jj] = (a[1][0][ii*9+jj]=='0'?0:1);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)if(s%9+ii <= n && s%9+jj <= n)m[s%9+ii][s%9+jj] = (a[1][1][ii*9+jj]=='0'?0:1);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)if(s%9+ii <= n && s%9+9+jj <= n)m[s%9+ii][s%9+9+jj] = (a[1][2][ii*9+jj]=='0'?0:1);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)if(s%9+9+ii <= n)m[s%9+9+ii][jj] = (a[2][0][ii*9+jj]=='0'?0:1);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)if(s%9+9+ii <= n && s%9+jj <= n)m[s%9+9+ii][s%9+jj] = (a[2][1][ii*9+jj]=='0'?0:1);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)if(s%9+9+ii <= n && s%9+9+jj <= n)m[s%9+9+ii][s%9+9+jj] = (a[2][2][ii*9+jj]=='0'?0:1);
int C = (n+1)*(n+1);
vector<int> p(C);
for(int ii=0;ii<C;ii++)p[ii] = ii;
for(int y=0;y<n;y++)for(int x=0;x<=n;x++) {
if(m[y][x] && m[y+1][x]) {
p[par(y*(n+1)+x,p)] = par((y+1)*(n+1)+x,p);
}
}
for(int y=0;y<=n;y++)for(int x=0;x<n;x++) {
if(m[y][x] && m[y][x+1]) {
p[par(y*(n+1)+x,p)] = par(y*(n+1)+x+1,p);
}
}
vector<int> cnt(C,0),cntv(C,0),cnth(C,0);
for(int y=0;y<=n;y++)for(int x=0;x<=n;x++)if(m[y][x])cnt[par(y*(n+1)+x,p)]++;
for(int y=0;y<n;y++)if(m[y][n])cntv[p[y*(n+1)+n]]++;
for(int x=0;x<n;x++)if(m[n][x])cnth[p[n*(n+1)+x]]++;
int ans = 0;
for(int ii=0;ii<C;ii++)if(cnt[ii] > 0 && cntv[ii] == 0 && cnth[ii] == 0)ans++;
queue<int> resq;
resq.push(m[n][n]);
int prev = -1;
if(m[n][n])prev = p[C-1];
for(int y=n-1;y>=0;y--) {
if(m[y][n]) {
if(prev == p[y*(n+1)+n]) {
resq.push(0);
resq.push(1);
}
else {
prev = p[y*(n+1)+n];
resq.push(1);
resq.push(cnth[p[y*(n+1)+n]]?1:0);
}
}
else {
resq.push(0);
resq.push(0);
}
}
prev = -1;
if(m[n][n])prev = p[C-1];
for(int x=n-1;x>=0;x--) {
if(m[n][x]) {
if(prev == p[n*(n+1)+x]) {
resq.push(0);
resq.push(1);
}
else {
prev = p[n*(n+1)+x];
resq.push(1);
resq.push(cntv[p[n*(n+1)+x]]?1:0);
}
}
else {
resq.push(0);
resq.push(0);
}
}
while(ans) {
resq.push(ans&1);
ans /= 2;
}
for(int ii=0;!resq.empty();ii++) {
res[ii] = '0'+resq.front();
resq.pop();
}
}
else if(n > 17) {
if(i == 0 && j == 2) {
vector<vector<int>> m(n+1,vector<int>(n+1));
for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)subf(ii,s%9+9+jj-n,a[0][0][ii*9+jj],n,m);
for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)subf(ii,s%9+9+9+jj-n,a[0][1][ii*9+jj],n,m);
for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)subf(ii,s%9+9+9+9+jj-n,a[0][2][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii,s%9+9+jj-n,a[1][0][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii,s%9+9+9+jj-n,a[1][1][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii,s%9+9+9+9+jj-n,a[1][2][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii,s%9+9+jj-n,a[2][0][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii,s%9+9+9+jj-n,a[2][1][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii,s%9+9+9+9+jj-n,a[2][2][ii*9+jj],n,m);
int C = (n+1)*(n+1);
vector<int> p(C);
for(int ii=0;ii<C;ii++)p[ii] = ii;
for(int y=0;y<n;y++)for(int x=0;x<=n;x++) {
if(m[y][x] && m[y+1][x]) {
p[par(y*(n+1)+x,p)] = par((y+1)*(n+1)+x,p);
}
}
for(int y=0;y<=n;y++)for(int x=0;x<n;x++) {
if(m[y][x] && m[y][x+1]) {
p[par(y*(n+1)+x,p)] = par(y*(n+1)+x+1,p);
}
}
vector<int> cnt(C,0),cntv(C,0),cnth(C,0);
for(int y=0;y<=n;y++)for(int x=0;x<=n;x++)if(m[y][x])cnt[par(y*(n+1)+x,p)]++;
for(int y=0;y<n;y++)if(m[y][0])cntv[p[y*(n+1)]]++;
for(int x=0;x<n;x++)if(m[n][x])cnth[p[n*(n+1)+x]]++;
int ans = 0;
for(int ii=0;ii<C;ii++)if(cnt[ii] > 0 && cntv[ii] == 0 && cnth[ii] == 0)ans++;
queue<int> resq;
resq.push(m[n][0]);
int prev = -1;
if(m[n][0])prev = p[n*(n+1)];
for(int y=n-1;y>=0;y--) {
if(m[y][0]) {
if(prev == p[y*(n+1)+0]) {
resq.push(0);
resq.push(1);
}
else {
prev = p[y*(n+1)+0];
resq.push(1);
resq.push(cnth[p[y*(n+1)+0]]?1:0);
}
}
else {
resq.push(0);
resq.push(0);
}
}
prev = -1;
if(m[n][0])prev = p[n*(n+1)];
for(int x=1;x<=n;x++) {
if(m[n][x]) {
if(prev == p[n*(n+1)+x]) {
resq.push(0);
resq.push(1);
}
else {
prev = p[n*(n+1)+x];
resq.push(1);
resq.push(cntv[p[n*(n+1)+x]]?1:0);
}
}
else {
resq.push(0);
resq.push(0);
}
}
while(ans) {
resq.push(ans&1);
ans /= 2;
}
for(int ii=0;!resq.empty();ii++) {
res[ii] = '0'+resq.front();
resq.pop();
}
}
else if(i == 2 && j == 2) {
vector<vector<int>> m(n+1,vector<int>(n+1));
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+9+jj-n,a[0][0][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+9+9+jj-n,a[0][1][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+9+9+9+jj-n,a[0][2][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+9+jj-n,a[1][0][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+9+9+jj-n,a[1][1][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+9+9+9+jj-n,a[1][2][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+9+ii-n,s%9+9+jj-n,a[2][0][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+9+ii-n,s%9+9+9+jj-n,a[2][1][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+9+ii-n,s%9+9+9+9+jj-n,a[2][2][ii*9+jj],n,m);
int C = (n+1)*(n+1);
vector<int> p(C);
for(int ii=0;ii<C;ii++)p[ii] = ii;
for(int y=0;y<n;y++)for(int x=0;x<=n;x++) {
if(m[y][x] && m[y+1][x]) {
p[par(y*(n+1)+x,p)] = par((y+1)*(n+1)+x,p);
}
}
for(int y=0;y<=n;y++)for(int x=0;x<n;x++) {
if(m[y][x] && m[y][x+1]) {
p[par(y*(n+1)+x,p)] = par(y*(n+1)+x+1,p);
}
}
vector<int> cnt(C,0),cntv(C,0),cnth(C,0);
for(int y=0;y<=n;y++)for(int x=0;x<=n;x++)if(m[y][x])cnt[par(y*(n+1)+x,p)]++;
for(int y=0;y<n;y++)if(m[y][0])cntv[p[y*(n+1)]]++;
for(int x=0;x<n;x++)if(m[0][x])cnth[p[x]]++;
int ans = 0;
for(int ii=0;ii<C;ii++)if(cnt[ii] > 0 && cntv[ii] == 0 && cnth[ii] == 0)ans++;
queue<int> resq;
resq.push(m[0][0]);
int prev = -1;
if(m[0][0])prev = p[0];
for(int y=1;y<=n;y++) {
if(m[y][0]) {
if(prev == p[y*(n+1)]) {
resq.push(0);
resq.push(1);
}
else {
prev = p[y*(n+1)];
resq.push(1);
resq.push(cnth[p[y*(n+1)]]?1:0);
}
}
else {
resq.push(0);
resq.push(0);
}
}
prev = -1;
if(m[0][0])prev = p[0];
for(int x=1;x<=n;x++) {
if(m[0][x]) {
if(prev == p[x]) {
resq.push(0);
resq.push(1);
}
else {
prev = p[x];
resq.push(1);
resq.push(cntv[p[x]]?1:0);
}
}
else {
resq.push(0);
resq.push(0);
}
}
while(ans) {
resq.push(ans&1);
ans /= 2;
}
for(int ii=0;!resq.empty();ii++) {
res[ii] = '0'+resq.front();
resq.pop();
}
}
else if(i == 2 && j == 0) {
vector<vector<int>> m(n+1,vector<int>(n+1));
for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)subf(s%9+9+ii-n,jj,a[0][0][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+jj,a[0][1][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+9+jj,a[0][2][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)subf(s%9+9+9+ii-n,jj,a[1][0][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+jj,a[1][1][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+9+jj,a[1][2][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)subf(s%9+9+9+9+ii-n,jj,a[2][0][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+9+ii-n,s%9+jj,a[2][1][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+9+ii-n,s%9+9+jj,a[2][2][ii*9+jj],n,m);
int C = (n+1)*(n+1);
vector<int> p(C);
for(int ii=0;ii<C;ii++)p[ii] = ii;
for(int y=0;y<n;y++)for(int x=0;x<=n;x++) {
if(m[y][x] && m[y+1][x]) {
p[par(y*(n+1)+x,p)] = par((y+1)*(n+1)+x,p);
}
}
for(int y=0;y<=n;y++)for(int x=0;x<n;x++) {
if(m[y][x] && m[y][x+1]) {
p[par(y*(n+1)+x,p)] = par(y*(n+1)+x+1,p);
}
}
vector<int> cnt(C,0),cntv(C,0),cnth(C,0);
for(int y=0;y<=n;y++)for(int x=0;x<=n;x++)if(m[y][x])cnt[par(y*(n+1)+x,p)]++;
for(int y=0;y<n;y++)if(m[y][n])cntv[p[y*(n+1)+n]]++;
for(int x=0;x<n;x++)if(m[0][x])cnth[p[x]]++;
int ans = 0;
for(int ii=0;ii<C;ii++)if(cnt[ii] > 0 && cntv[ii] == 0 && cnth[ii] == 0)ans++;
queue<int> resq;
resq.push(m[0][n]);
int prev = -1;
if(m[0][n])prev = p[n];
for(int y=1;y<=n;y++) {
if(m[y][n]) {
if(prev == p[y*(n+1)+n]) {
resq.push(0);
resq.push(1);
}
else {
prev = p[y*(n+1)+n];
resq.push(1);
resq.push(cnth[p[y*(n+1)+n]]?1:0);
}
}
else {
resq.push(0);
resq.push(0);
}
}
prev = -1;
if(m[0][0])prev = p[0];
for(int x=n-1;x>=0;x--) {
if(m[0][x]) {
if(prev == p[x]) {
resq.push(0);
resq.push(1);
}
else {
prev = p[x];
resq.push(1);
resq.push(cntv[p[x]]?1:0);
}
}
else {
resq.push(0);
resq.push(0);
}
}
while(ans) {
resq.push(ans&1);
ans /= 2;
}
for(int ii=0;!resq.empty();ii++) {
res[ii] = '0'+resq.front();
resq.pop();
}
}
}
else {
if(i == 0 && j == 1) {
vector<vector<int>> m(n+1,vector<int>(n+1));
for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)subf(ii,s%9+jj-n,a[0][0][ii*9+jj],n,m);
for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)subf(ii,s%9+9+jj-n,a[0][1][ii*9+jj],n,m);
for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)subf(ii,s%9+9+9+jj-n,a[0][2][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii,s%9+jj-n,a[1][0][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii,s%9+9+jj-n,a[1][1][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii,s%9+9+9+jj-n,a[1][2][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii,s%9+jj-n,a[2][0][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii,s%9+9+jj-n,a[2][1][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii,s%9+9+9+jj-n,a[2][2][ii*9+jj],n,m);
int C = (n+1)*(n+1);
vector<int> p(C);
for(int ii=0;ii<C;ii++)p[ii] = ii;
for(int y=0;y<n;y++)for(int x=0;x<=n;x++) {
if(m[y][x] && m[y+1][x]) {
p[par(y*(n+1)+x,p)] = par((y+1)*(n+1)+x,p);
}
}
for(int y=0;y<=n;y++)for(int x=0;x<n;x++) {
if(m[y][x] && m[y][x+1]) {
p[par(y*(n+1)+x,p)] = par(y*(n+1)+x+1,p);
}
}
vector<int> cnt(C,0),cntv(C,0),cnth(C,0);
for(int y=0;y<=n;y++)for(int x=0;x<=n;x++)if(m[y][x])cnt[par(y*(n+1)+x,p)]++;
for(int y=0;y<n;y++)if(m[y][0])cntv[p[y*(n+1)]]++;
for(int x=0;x<n;x++)if(m[n][x])cnth[p[n*(n+1)+x]]++;
int ans = 0;
for(int ii=0;ii<C;ii++)if(cnt[ii] > 0 && cntv[ii] == 0 && cnth[ii] == 0)ans++;
queue<int> resq;
resq.push(m[n][0]);
int prev = -1;
if(m[n][0])prev = p[n*(n+1)];
for(int y=n-1;y>=0;y--) {
if(m[y][0]) {
if(prev == p[y*(n+1)+0]) {
resq.push(0);
resq.push(1);
}
else {
prev = p[y*(n+1)+0];
resq.push(1);
resq.push(cnth[p[y*(n+1)+0]]?1:0);
}
}
else {
resq.push(0);
resq.push(0);
}
}
prev = -1;
if(m[n][0])prev = p[n*(n+1)];
for(int x=1;x<=n;x++) {
if(m[n][x]) {
if(prev == p[n*(n+1)+x]) {
resq.push(0);
resq.push(1);
}
else {
prev = p[n*(n+1)+x];
resq.push(1);
resq.push(cntv[p[n*(n+1)+x]]?1:0);
}
}
else {
resq.push(0);
resq.push(0);
}
}
while(ans) {
resq.push(ans&1);
ans /= 2;
}
for(int ii=0;!resq.empty();ii++) {
res[ii] = '0'+resq.front();
resq.pop();
}
}
else if(i == 1 && j == 1) {
vector<vector<int>> m(n+1,vector<int>(n+1));
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii-n,s%9+jj-n,a[0][0][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii-n,s%9+9+jj-n,a[0][1][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii-n,s%9+9+9+jj-n,a[0][2][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+jj-n,a[1][0][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+9+jj-n,a[1][1][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+9+9+jj-n,a[1][2][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+jj-n,a[2][0][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+9+jj-n,a[2][1][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+9+9+jj-n,a[2][2][ii*9+jj],n,m);
int C = (n+1)*(n+1);
vector<int> p(C);
for(int ii=0;ii<C;ii++)p[ii] = ii;
for(int y=0;y<n;y++)for(int x=0;x<=n;x++) {
if(m[y][x] && m[y+1][x]) {
p[par(y*(n+1)+x,p)] = par((y+1)*(n+1)+x,p);
}
}
for(int y=0;y<=n;y++)for(int x=0;x<n;x++) {
if(m[y][x] && m[y][x+1]) {
p[par(y*(n+1)+x,p)] = par(y*(n+1)+x+1,p);
}
}
vector<int> cnt(C,0),cntv(C,0),cnth(C,0);
for(int y=0;y<=n;y++)for(int x=0;x<=n;x++)if(m[y][x])cnt[par(y*(n+1)+x,p)]++;
for(int y=0;y<n;y++)if(m[y][0])cntv[p[y*(n+1)]]++;
for(int x=0;x<n;x++)if(m[0][x])cnth[p[x]]++;
int ans = 0;
for(int ii=0;ii<C;ii++)if(cnt[ii] > 0 && cntv[ii] == 0 && cnth[ii] == 0)ans++;
queue<int> resq;
resq.push(m[0][0]);
int prev = -1;
if(m[0][0])prev = p[0];
for(int y=1;y<=n;y++) {
if(m[y][0]) {
if(prev == p[y*(n+1)]) {
resq.push(0);
resq.push(1);
}
else {
prev = p[y*(n+1)];
resq.push(1);
resq.push(cnth[p[y*(n+1)]]?1:0);
}
}
else {
resq.push(0);
resq.push(0);
}
}
prev = -1;
if(m[0][0])prev = p[0];
for(int x=1;x<=n;x++) {
if(m[0][x]) {
if(prev == p[x]) {
resq.push(0);
resq.push(1);
}
else {
prev = p[x];
resq.push(1);
resq.push(cntv[p[x]]?1:0);
}
}
else {
resq.push(0);
resq.push(0);
}
}
while(ans) {
resq.push(ans&1);
ans /= 2;
}
for(int ii=0;!resq.empty();ii++) {
res[ii] = '0'+resq.front();
resq.pop();
}
}
else if(i == 1 && j == 0) {
vector<vector<int>> m(n+1,vector<int>(n+1));
for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)subf(s%9+ii-n,jj,a[0][0][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii-n,s%9+jj,a[0][1][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii-n,s%9+9+jj,a[0][2][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)subf(s%9+9+ii-n,jj,a[1][0][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+jj,a[1][1][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+9+jj,a[1][2][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)subf(s%9+9+9+ii-n,jj,a[2][0][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+jj,a[2][1][ii*9+jj],n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+9+jj,a[2][2][ii*9+jj],n,m);
int C = (n+1)*(n+1);
vector<int> p(C);
for(int ii=0;ii<C;ii++)p[ii] = ii;
for(int y=0;y<n;y++)for(int x=0;x<=n;x++) {
if(m[y][x] && m[y+1][x]) {
p[par(y*(n+1)+x,p)] = par((y+1)*(n+1)+x,p);
}
}
for(int y=0;y<=n;y++)for(int x=0;x<n;x++) {
if(m[y][x] && m[y][x+1]) {
p[par(y*(n+1)+x,p)] = par(y*(n+1)+x+1,p);
}
}
vector<int> cnt(C,0),cntv(C,0),cnth(C,0);
for(int y=0;y<=n;y++)for(int x=0;x<=n;x++)if(m[y][x])cnt[par(y*(n+1)+x,p)]++;
for(int y=0;y<n;y++)if(m[y][n])cntv[p[y*(n+1)+n]]++;
for(int x=0;x<n;x++)if(m[0][x])cnth[p[x]]++;
int ans = 0;
for(int ii=0;ii<C;ii++)if(cnt[ii] > 0 && cntv[ii] == 0 && cnth[ii] == 0)ans++;
queue<int> resq;
resq.push(m[0][n]);
int prev = -1;
if(m[0][n])prev = p[n];
for(int y=1;y<=n;y++) {
if(m[y][n]) {
if(prev == p[y*(n+1)+n]) {
resq.push(0);
resq.push(1);
}
else {
prev = p[y*(n+1)+n];
resq.push(1);
resq.push(cnth[p[y*(n+1)+n]]?1:0);
}
}
else {
resq.push(0);
resq.push(0);
}
}
prev = -1;
if(m[0][0])prev = p[0];
for(int x=n-1;x>=0;x--) {
if(m[0][x]) {
if(prev == p[x]) {
resq.push(0);
resq.push(1);
}
else {
prev = p[x];
resq.push(1);
resq.push(cntv[p[x]]?1:0);
}
}
else {
resq.push(0);
resq.push(0);
}
}
while(ans) {
resq.push(ans&1);
ans /= 2;
}
for(int ii=0;!resq.empty();ii++) {
res[ii] = '0'+resq.front();
resq.pop();
}
}
}
}
else {
// last
if(true) {
vector<vector<int>> m(n+n+1,vector<int>(n+n+1));
for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<s%9;jj++)subf(ii,jj,a[0][0][ii*9+jj],n+n,m);
for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)subf(ii,s%9+jj,a[0][1][ii*9+jj],n+n,m);
for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)subf(ii,s%9+9+jj,a[0][2][ii*9+jj],n+n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)subf(s%9+ii,jj,a[1][0][ii*9+jj],n+n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii,s%9+jj,a[1][1][ii*9+jj],n+n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii,s%9+9+jj,a[1][2][ii*9+jj],n+n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)subf(s%9+9+ii,jj,a[2][0][ii*9+jj],n+n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii,s%9+jj,a[2][1][ii*9+jj],n+n,m);
for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii,s%9+9+jj,a[2][2][ii*9+jj],n+n,m);
int C = (n+n+1)*(n+n+1);
vector<int> p(C);
for(int ii=0;ii<C;ii++)p[ii] = ii;
for(int y=0;y<n+n;y++)for(int x=0;x<=n+n;x++) {
if(m[y][x] && m[y+1][x]) {
p[par(y*(n+n+1)+x,p)] = par((y+1)*(n+n+1)+x,p);
}
}
for(int y=0;y<=n+n;y++)for(int x=0;x<n+n;x++) {
if(m[y][x] && m[y][x+1]) {
p[par(y*(n+n+1)+x,p)] = par(y*(n+n+1)+x+1,p);
}
}
vector<int> cnt(C,0);
for(int y=0;y<=n+n;y++)for(int x=0;x<=n+n;x++)if(m[y][x])cnt[par(y*(n+n+1)+x,p)]++;
int ans = 0;
for(int ii=0;ii<C;ii++)if(cnt[ii])ans++;
queue<int> resq;
while(ans) {
resq.push(ans&1);
ans /= 2;
}
for(int ii=0;!resq.empty();ii++) {
res[ii] = '0'+resq.front();
resq.pop();
}
}
else {
}
}
return res;
}
