#include "prison.h"
#include <vector>
#include <iostream>
#include <cassert>
#include <algorithm>
using namespace std;
int get_bit(int x, int bit, int base=2) {
vector<int> lst;
while(x>0) {
lst.push_back(x%base);
x/=base;
}
return (bit>=(int)lst.size()?0:lst[bit]);
}
std::vector<std::vector<int>> devise_strategy(int N) {
//~ cerr<<get_bit(4, 0)<<"\n";
//~ exit(0);
const int BASE=3;
const int START=7;
//~ std::cerr<<get_bit(2, START, BASE)<<"\n";
int x=22;
std::vector<std::vector<int>> s(x+1, std::vector<int>(N+1, 0));
//~ cerr<<"digraph G {\n";
for(int i=0;i<=x;++i) {
if(i==0) {
s[i][0]=0;
for(int j=1;j<=N;++j) {
s[i][j]=1+get_bit(j, START, BASE);
//~ cerr<<i<<" -> "<<s[i][j]<<"\n";
}
}else {
int bit=START-(i-1)/BASE;
int bag=(bit&1)^1;
int have=(i-1)%BASE;
if(i==x) have++; //mod3
s[i][0]=bag;
int THIS=bag==0?-1:-2;
int OTHER=bag==0?-2:-1;
//~ if(i==1) cerr<<have<<"\n";
for(int j=1;j<=N;++j) {
int curr=get_bit(j,bit, BASE);
//~ if(i==1) cerr<<curr<<"\n";
if(curr>have) {
s[i][j]=OTHER;
}else if(curr<have) {
s[i][j]=THIS;
}else {
int nxt=get_bit(j, bit-1, BASE);
if(bit-1==0) {
if(nxt==0) {
s[i][j]=THIS;
}else if(nxt==2) {
s[i][j]=OTHER;
}else {
s[i][j]=22;
}
}else {
s[i][j]=BASE*(START-bit+1)+1+nxt;
if(i==22) s[i][j]=THIS;
}
}
}
}
}
//~ for(auto i:s) {
//~ for(auto j:i) cerr<<j<<" ";
//~ cerr<<"\n";
//~ }
//~ cerr<<"}\n";
return s;
}
