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