#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>otg;
vector<int>v;
int n,dp[5005],mas[10],group[30];
void make_dp()
{
for(int i=3;i<=n;i++)
{
dp[i]=100000;
for(int j=(i+1)/2;j<i;j++)
{
dp[i]=min(dp[i],dp[j]+2);
}
for(int j=(i+2)/3;j<i;j++)
{
dp[i]=min(dp[i],dp[j]+3);
}
}
}
void prec()
{
mas[0]=5001;
mas[1]=1944;
mas[2]=648;
mas[3]=216;
mas[4]=72;
mas[5]=24;
mas[6]=8;
mas[7]=8;
mas[8]=4;
mas[9]=2;
for(int i=0;i<=22;i++)otg.push_back(v);
otg[0].push_back(0);
group[0]=1;
for(int i=1;i<=18;i++)
{
otg[i].push_back(((i+2)/3)%2);
group[i]=(i+5)/3;
}
otg[19].push_back(1);
otg[20].push_back(1);
otg[21].push_back(0);
otg[22].push_back(0);
group[19]=8;
group[20]=8;
group[21]=9;
group[22]=9;
}
void fil(int ind)
{
int gr=group[ind],gran=mas[gr],st,prev=mas[gr-1],cur,bag=otg[ind][0]+1;
for(int i=1;i<=n;i++)
{
if(ind)
{
if(ind<=18)st=(ind-1)%3;
else st=(ind-1)%2;
cur=(i%mas[gr-2])/prev;
if(st>cur)
{
otg[ind].push_back(-bag);
continue;
}
if(st<cur)
{
otg[ind].push_back(-(bag%2+1));
continue;
}
if(ind==21||ind==22)
{
cur=i%prev+1;
cur=cur/2;
if(!cur)otg[ind].push_back(-bag);
else otg[ind].push_back(-(bag%2+1));
continue;
}
}
cur=i%prev;
cur=cur/gran;
if(ind<=18)otg[ind].push_back(((ind+2)/3)*3+cur+1);
else otg[ind].push_back(((ind+1)/2)*2+cur+1);
}
}
vector<vector<int>> devise_strategy(int N)
{
n=N;
prec();
for(int i=0;i<=22;i++)
{
fil(i);
}
for(int i=0;i<=22;i++)
{
//cout<<i<<" | ";
for(int j=0;j<=n;j++)
{
//cout<<otg[i][j]<<" ";
}
//cout<<endl;
}
//cout<<endl;
//return otg;
return otg;
}
