#include "prison.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 30;
vector < vector<int > > v;
void go(ll x, ll l , ll r, ll wh)
{
v[x][0] = wh;
ll mid = (l+r)/2;
ll newl, newr;
if(x%2==1)
{
for(int i = mid+1; i <= r; i++)
if(wh==0) v[x][i] = -2; else v[x][i] = -1;
newl = l, newr = mid;
}
else
{
for(int i = l; i <= mid; i++)
if(wh==0) v[x][i] = -1; else v[x][i] = -2;
newl = mid+1, newr = r;
}
if(newr==newl+1)
{
if(wh==0) v[x][newl] = -1, v[x][newr] = -2;
else v[x][newl] = -2, v[x][newr] = -1;
return;
}
if(newl==newr) return;
ll odd = x + x%2 + 1;
ll even = x+x%2+2;
for(int i = newl; i<= (newl+newr)/2; i++) v[x][i] = odd;
for(int i = (newl+newr)/2+1; i <= newr; i++) v[x][i] = even;
go(odd,newl,newr,!wh);
go(even,newl,newr,!wh);
}
ll n;
std::vector<std::vector<int>> devise_strategy(int N) {
n = N;
ll mysize = log2(n)*2;
v.resize(mysize+1,vector<int> (N+1));
v[0][0] = 0;
ll mid = (1+n)/2;
for(int i = 1; i <= mid; i++) v[0][i] = 1;
for(int i = mid+1; i <= n; i++) v[0][i] = 2;
go(1,1,n,1);
go(2,1,n,1);
// for(int i = 0; i <= mysize; i++)
// for(int j = 0; j <= N; j++) cout << v[i][j] << " "; cout << endl;
return v;
//return {std::vector<int>(N + 1, 0)};
}
