#include "prison.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define vout(x) for(auto u : x)cout<<u<<' ';cout<<'\n';
using namespace std;
const vi divv = {3,3,3,3,3,2,2,1};
const vi ad = {1,4,7,10,13,16,19,20};
const vi chec = {0,1,1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,1,1,0};
vector<vi>v(21);
void solve(int l, int r, int layer, int dex){
if(divv[layer] == 3){
for(int j = ad[layer]; j<=ad[layer] + 2; j++){
if(j > dex){
for(int i = l; i<=r; i++){
if(layer % 2 == 0){
v[j][i] = -2;
}
else v[j][i] = -1;
}
}
else if(j < dex){
for(int i = l; i<=r; i++){
if(layer % 2 == 0){
v[j][i] = -1;
}
else v[j][i] = -2;
}
}
else{
if(divv[layer + 1] == 3){
int a = l + (r - l + 1) / 3;
int b = l + (r - l + 1) / 3 * 2;
for(int i = l; i<=r; i++){
if(i < a)v[j][i] = ad[layer + 1];
else if(i < b)v[j][i] = ad[layer + 1] + 1;
else v[j][i] = ad[layer + 1] + 2;
}
if(layer % 2 == 0){
v[j][l] = -2;
v[j][a-1] = -1;
v[j][a] = -2;
v[j][b-1] = -1;
v[j][b] = -2;
v[j][r] = -1;
}
else{
v[j][l] = -1;
v[j][a-1] = -2;
v[j][a] = -1;
v[j][b-1] = -2;
v[j][b] = -1;
v[j][r] = -2;
}
solve(l+1, a-2, layer + 1, ad[layer + 1]);
solve(a+1, b-2, layer + 1, ad[layer + 1] + 1);
solve(b+1, r-1, layer + 1, ad[layer + 1] + 2);
}
else{
int mid = (l + r) / 2;
for(int i = l; i<=r; i++){
if(i <= mid)v[j][i] = ad[layer + 1];
else v[j][i] = ad[layer + 1] + 1;
}
if(layer % 2 == 0){
v[j][l] = -2;
v[j][mid] = -1;
v[j][mid + 1] = -2;
v[j][r] = -1;
}
else{
v[j][l] = -1;
v[j][mid] = -2;
v[j][mid + 1] = -1;
v[j][r] = -2;
}
solve(l, mid, layer + 1, ad[layer + 1]);
solve(mid + 1, r, layer + 1, ad[layer + 1] + 1);
}
}
}
}
else if(divv[layer] == 2){
for(int j = ad[layer]; j<=ad[layer] + 1; j++){
if(j > dex){
for(int i = l; i<=r; i++){
if(layer % 2 == 0){
v[j][i] = -2;
}
else v[j][i] = -1;
}
}
else if(j < dex){
for(int i = l; i<=r; i++){
if(layer % 2 == 0){
v[j][i] = -1;
}
else v[j][i] = -2;
}
}
else{
if(divv[layer + 1] == 1){
for(int i = l; i<=r; i++){
v[j][i] = ad[layer + 1];
}
if(layer % 2 == 0){
v[j][l] = -2;
v[j][r] = -1;
}
else{
v[j][l] = -1;
v[j][r] = -2;
}
solve(l + 1, r - 1, layer + 1, ad[layer + 1]);
}
else{
int mid = (l + r) / 2;
for(int i = l; i<=r; i++){
if(i <= mid)v[j][i] = ad[layer + 1];
else v[j][i] = ad[layer + 1] + 1;
}
if(layer % 2 == 0){
v[j][l] = -2;
v[j][mid] = -1;
v[j][mid + 1] = -2;
v[j][r] = -1;
}
else{
v[j][l] = -1;
v[j][mid] = -2;
v[j][mid + 1] = -1;
v[j][r] = -2;
}
solve(l, mid, layer + 1, ad[layer + 1]);
solve(mid + 1, r, layer + 1, ad[layer + 1] + 1);
}
}
}
}
else{
if(l != r){
if(layer % 2 == 0){
v[dex][l] = -2;
v[dex][r] = -1;
}
else{
v[dex][l] = -1;
v[dex][r] = -2;
}
}
}
}
std::vector<std::vector<int>> devise_strategy(int N) {
f0r(i, 21)v[i].resize(N+1);
f0r(i, 21)v[i][0] = chec[i];
int a = N / 3;
int b = N / 3 * 2;
FOR(i, 1, N+1){
if(i < a)v[0][i] = 1;
else if(i < b)v[0][i] = 2;
else v[0][i] = 3;
}
solve(1, a-1, 0, 1);
solve(a, b-1, 0, 2);
solve(b, N, 0, 3);
return v;
}
