#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())
const int stp = 21;
int N;
vector<string> addr; //'L' = left end, 'R' = right end,
//'0' = part 0, '1' = part 1, '2' = part 2
vi dp(1+stp);
vi inv(1 + 6'000);
vi spl(1+stp);
vi dep;
void selfmax(int& a, int b)
{
a = max(a, b);
}
void build_tree(int l, int r, int i)
{
// cerr << "build tree " << l << ' ' << r << ' ' << i << " : " << dp[i] << '\n';
assert(l != r);
addr[l].push_back('L');
l++;
addr[r].push_back('R');
r--;
if(i == 1)
{
return;
}
else if(i == 2)
{
addr[l].push_back('0');
addr[l+1].push_back('0');
build_tree(l, l+1, 1);
}
else
{
int k;
if(dp[i] == 3*dp[i-3] + 2)
k = 3;
else
k = 2;
int j = (r-l+1)/k;
for(int ki = 0; ki < k; ki++)
{
int l1 = l + j*ki;
int r1 = l + j*(ki+1) - 1;
for(int n = l1; n <= r1; n++)
addr[n].push_back('0' + ki);
build_tree(l1, r1, i-k);
}
}
}
vvi devise_strategy(int N_)
{
dp[0] = -100;
dp[1] = 2;
dp[2] = 4;
for(int i = 3; i <= stp; i++)
{
if(i-3 >= 1)
selfmax(dp[i], 3*dp[i-3] + 2);
if(i-2 >= 1)
selfmax(dp[i], 2*dp[i-2] + 2);
if(dp[i] == 3*dp[i-3] + 2)
spl[i] = 3;
else
spl[i] = 2;
}
spl[2] = 1;
spl[1] = 0;
for(int i = 1; i <= stp; i++)
inv[dp[i]] = i;
// for(int i = stp; i >= 1; i--)
// cerr << dp[i] << " : " << spl[i] << '\n';
// cerr << "\n\n\n\n";
N = dp[stp];
// cerr << "N value = " << N << '\n';
addr = vector<string>(1+N, "");
build_tree(1, N, stp);
// cerr << "terminate\n";
// for(int i = 1; i <= N; i++)
// cerr << i << " : " << addr[i] << '\n';
int x = dp[stp];
vvi res(stp, vi(1+N, 0));
vi depsiz;
vi depspl;
vvi depind;
// cerr << "\n\n\n";
for(int z = N; z >= 3; z = (z-2)/spl[inv[z]])
{
depsiz.push_back(z);
depspl.push_back(spl[inv[z]]);
// cerr << z << " : " << spl[inv[z]] << '\n';
}
// cerr << 2 << " : " << 1 << '\n';
depsiz.push_back(2);
depspl.push_back(1);
// cerr << "\n\n\n";
int u = 1;
for(int d = 0; d < sz(depsiz)-1; d++)
{
depind.push_back({});
for(int e = 0; e < depspl[d]; e++)
{
depind[d].push_back(u++);
}
}
// cerr << "u = " << u << '\n';
// depind.push_back({{u++}});
//person 0, checks A
res[0][0] = 0;
for(int i = 1; i <= N; i++)
{
if(addr[i][0] == 'L')
res[0][i] = -1;
else if(addr[i][0] == 'R')
res[0][i] = -2;
else
{
res[0][i] = depind[0][ addr[i][0] - '0' ];
}
}
// cerr << "done\n";
// cerr << "sz = " << sz(depsiz) << '\n';
for(int d = 0; d < sz(depsiz)-1; d++)
//even depth, check B odd depth, check A
{
for(int z = 0; z < depspl[d]; z++)
{
int xi = depind[d][z];
// cerr << d << ", " << z << " -> " << xi << '\n';
// cerr << "xi = " << xi << '\n';
//d even -> check A, odd -> check B
if(d % 2 == 0)
res[xi][0] = 1;
else
res[xi][1] = 0;
for(int i = 1; i <= N; i++)
{
// cerr << "i = " << i << '\n';
// if(xi == 1 && i == 9)
// {
// cerr << "z = " << z << '\n';
// cerr << "hello, " << addr[i][d] << '\n';
// }
// cerr << "i = " << i << '\n';
if(sz(addr[i]) - 1 < d)
{
res[xi][i] = 0;
}
if(addr[i][d] == 'L')
{
// cerr << "case 1\n";
if(d % 2 == 0)
res[xi][i] = -2;
else
res[xi][i] = -1;
}
else if(addr[i][d] == 'R')
{
// cerr << "case 2\n";
if(d % 2 == 0)
res[xi][i] = -1;
else
res[xi][i] = -2;
}
else if(addr[i][d] - '0' < z)
{
if(d % 2 == 0)
res[xi][i] = -2;
else
res[xi][i] = -1;
}
else if(addr[i][d] - '0' > z)
{
if(d % 2 == 0)
res[xi][i] = -1;
else
res[xi][i] = -2;
}
else if(addr[i][d] - '0' == z)
{
// cerr << "case 3\n";
// cerr << i << " : " << d+1 << ' ' << sz(addr[i]) << '\n';
if(addr[i][d+1] == 'L')
{
if(d % 2 == 0)
res[xi][i] = -2;
else
res[xi][i] = -1;
}
else if(addr[i][d+1] == 'R')
{
if(d % 2 == 0)
res[xi][i] = -1;
else
res[xi][i] = -2;
}
else
res[xi][i] = depind[d+1][addr[i][d+1] - '0'];
}
}
// cerr << "z done\n";
}
// cerr << "d = " << d << " done\n";
}
// int ld = sz(depsiz) - 1;
// int lx = stp-1;
// cerr << "\n\n\n\n\n\n";
// cerr << "ld = " << ld << '\n';
// if(ld % 2 == 0)
// {
// res[ld][0] = 1;
// for(int i = 1; i <= N; i++)
// {
// if(sz(addr[i]) - 1 < ld)
// {
// res[lx][i] = 0;
// }
// else if(addr[i][ld] == 'L')
// res[lx][i] = -2;
// else
// res[lx][i] = -1;
// }
// }
// else
// {
// res[ld][0] = 0;
// for(int i = 1; i <= N; i++)
// {
// if(sz(addr[i]) - 1 < ld)
// {
// res[lx][i] = 0;
// }
// else if(addr[i][ld] == 'L')
// res[lx][i] = -1;
// else
// res[lx][i] = -2;
// }
// }
for(int xi = 0; xi < stp; xi++)
res[xi].resize(1+N_);
// cerr << "res size = " << sz(res) << '\n';
// for(vi f : res)
// cerr << sz(f) << '\n';
// cerr << "original N = " << N_ << '\n';
// for(int xi = 0; xi < stp; xi++)
// {
// for(int u : res[xi])
// cerr << u << ' ';
// cerr << '\n';
// }
// cerr << addr[7] << "\n" << addr[8] << '\n';
// cerr << "columns\n";
// for(int xv = 0; xv < stp; xv++)
// cerr << res[xv][7] << ' ' << res[xv][8] << '\n';
// cerr << "\n\n";
return res;
}
