#include "prison.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> ans;
int n;
void fin(int l, int r, int i){
int z = (i+2)/3;
int box = ((i+2)%6 < 3);
ans[i][l] = ~box;
ans[i][r] = ~(int)(!box);
l++;
r--;
if(l > r)return;
ans[z*3+1][l-1] = ans[z*3+2][l-1] = ans[z*3+3][l-1] = ~(int)(!box);
ans[z*3+1][r+1] = ans[z*3+2][r+1] = ans[z*3+3][r+1] = ~box;
int d1 = l+(r-l)/3, d2 = r - (r-l)/3;
for(int j = l; j <= d1; ++j){ans[i][j] = z*3+1;ans[z*3+2][j] = ans[z*3+3][j] = ~(int)(!box);}
for(int j = d1+1; j <= d2; ++j){ans[i][j] = z*3+2;ans[z*3+1][j] = ~box; ans[z*3+3][j] = ~(int)(!box);}
for(int j = d2+1; j <= r; ++j){ans[i][j] = z*3+3; ans[z*3+1][j] = ans[z*3+2][j] = ~box;}
fin(l,d1,z*3+1);
fin(d1+1,d2,z*3+2);
fin(d2+1,r,z*3+3);
}
vector<vector<int>> devise_strategy(int N) {
n = N;
ans.resize(22,vector<int>(N+1,0));
for(int i = 0; i < 22; ++i)ans[i][0] = ((i+2)%6 < 3);
fin(1,N,0);
return ans;
}
