#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int P[]={0, 2, 3, 3, 3, 3, 2, 2, 2};
int Q[]={0, 2, 5, 8, 11, 14, 16, 18, 20};
int A[21][5023];
int B[10][5023];
void f(int pos, int l, int r)
{
B[pos][l]=-1; B[pos][r]=-2;
if(l+2>r) return;
int p=(r-l-1)/P[pos];
for(int i=l+1; i<r; i++)
{
B[pos][i]=(i-l-1)/p+Q[pos-1]+1;
}
for(int i=l+1; i<r; i+=p) f(pos+1, i, i+p-1);
}
vector<vector<int>> devise_strategy(int N)
{
f(1, 1, 5022);
A[0][0]=0;
A[0][1]=-1; A[0][5022]=-2;
for(int i=2; i<=5021; i++) A[0][i]=B[1][i];
for(int i=1; i<=8; i++)
{
for(int j=Q[i-1]+1; j<=Q[i]; j++)
{
int t=A[j][0]=i%2;
for(int k=1; k<=5022; k++)
{
if(B[i][k]==-1)
{
if(t) A[j][k]=-2;
else A[j][k]=-1;
}
else if(B[i][k]==-2)
{
if(t) A[j][k]=-1;
else A[j][k]=-2;
}
else if(B[i][k]<j)
{
if(t) A[j][k]=-2;
else A[j][k]=-1;
}
else if(B[i][k]>j)
{
if(t) A[j][k]=-1;
else A[j][k]=-2;
}
else
{
if(B[i+1][k]==-1)
{
if(t) A[j][k]=-2;
else A[j][k]=-1;
}
else if(B[i+1][k]==-2)
{
if(t) A[j][k]=-1;
else A[j][k]=-2;
}
else A[j][k]=B[i+1][k];
}
}
}
}
vector<vector<int>> ans=vector<vector<int>>(21, vector<int>(N+1));
for(int i=0; i<=20; i++) for(int j=0; j<=N; j++) ans[i][j]=A[i][j];
return ans;
}
