#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> devise_strategy(int N) {
int k = __lg(N);
int m = 2*k;
vector<vector<int>> ans(m+1,vector<int>(N+1));
for(int see = 0;see <= m;see++){
int current_bit = (see+1)/2;
int nxt_bit = current_bit-1;
if(nxt_bit < 0) nxt_bit = k;
ans[see][0] = (k-nxt_bit)%2;// current looking at 0:A,1:B
for(int bag = 1;bag <= N;bag++){
int nv = ((1 << nxt_bit)&bag)!=0;
int cv = ((1 << current_bit)&bag)!=0;
if(see == 0){
ans[see][bag] = 2*nxt_bit-nv;
continue;
}
if(see%2 != cv){
// got the answer;
if((cv > see%2) == ans[see][0]){
ans[see][bag] = -1;
}else{
ans[see][bag] = -2;
}
}else if(see <= 2){
// must have the answer;
if((bag&1) == ans[see][0]){
ans[see][bag] = -1;
}else{
ans[see][bag] = -2;
}
}else{
ans[see][bag] = 2*nxt_bit-nv;
}
}
}
return ans;
}
