#include "prison.h"
#include<bits/stdc++.h>
using namespace std;
int base=3, lg=0;
void calc(int N){
long long pw=base;
while(pw<=N) {
pw*=base;
lg++;
}
}
struct S {
int idx, val;
S(){}
S(int v) {
v--;
val=v%(base);
idx=v/(base);
}
};
int toInt(S s) {
return s.idx*(base)+s.val+1;
}
int getB(int n, int idx) {
vector<int> v;
for(int i = 0;i<=lg;i++) {
v.push_back(n%base);
n/=base;
}
reverse(v.begin(),v.end());
return v[idx];
}
std::vector<std::vector<int>> devise_strategy(int N) {
calc(5000);
int X=lg*(base)+base;
cerr << X << endl;
vector<vector<int>> s(X+1, vector<int> (N+1));
for(int i = 0;i<=X;i++) {
S wh=S(i);
if(wh.idx%2==0) {
s[i][0]=0;
}
else {
s[i][0]=1;
}
if(i) {
for(int sz=1;sz<=N;sz++) {
int val=getB(sz, wh.idx);
if(val<wh.val) {
if(wh.idx%2==0) {
s[i][sz]=-1;
}
else s[i][sz]=-2;
}
else if(val>wh.val) {
if(wh.idx%2==0) {
s[i][sz]=-2;
}
else s[i][sz]=-1;
}
else if(wh.idx==lg) {
s[i][sz]=-1;
}
else {
S res;
res.val=getB(sz,wh.idx+1);
res.idx=wh.idx+1;
if(res.idx==lg and res.val==2) {
if(res.idx%2==1)s[i][sz]=-2;
else s[i][sz]=-1;
}
else if(res.idx==lg and res.val==0) {
if(res.idx%2==1)s[i][sz]=-1;
else s[i][sz]=-2;
}
else s[i][sz]=toInt(res);
}
}
}
else {
s[i][0]=1;
for(int sz=1;sz<=N;sz++) {
S res;
res.val=getB(sz,wh.idx);
res.idx=0;
s[i][sz]=toInt(res);
}
}
}
return s;
}
