#include <bits/stdc++.h>
#include "prison.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int K = 13;
vector<vector<int>> devise_strategy(int n) {
vector<vector<int>> res(2*K+1, vector<int>(n+1, 0));
// 2*i+1 - ith bit set
// 2*i+2 - ith bit not set
// for i=0, 2, 4, ... we check in A
// for i=1, 3, 5, ... we check in B
res[0][0]=(K-1)%2;
for (int i=1; i<=n; ++i) {
int x=K-1;
if (i&(1<<x)) res[0][i]=2*x+1;
else res[0][i]=2*x+2;
}
for (int i=0; i<K; ++i) {
int s=2*i+1;
if (i%2 == 0) {
res[s][0]=1; // we know ith bit of A so we need to check B
for (int j=1; j<=n; ++j) {
if (j&(1<<i)) {
int x=i-1;
if (j&(1<<x)) res[s][j]=2*x+1;
else res[s][j]=2*x+2;
} else res[s][j]=-2;
}
} else {
res[s][0]=0;
for (int j=1; j<=n; ++j) {
if (j&(1<<i)) {
int x=i-1;
if (j&(1<<x)) res[s][j]=2*x+1;
else res[s][j]=2*x+2;
} else res[s][j]=-1;
}
}
s=2*i+2;
if (i%2 == 0) {
res[s][0]=1;
for (int j=1; j<=n; ++j) {
if (j&(1<<i)) res[s][j]=-1;
else {
int x=i-1;
if (j&(1<<x)) res[s][j]=2*x+1;
else res[s][j]=2*x+2;
}
}
} else {
res[s][0]=0;
for (int j=1; j<=n; ++j) {
if (j&(1<<i)) res[s][j]=-2;
else {
int x=i-1;
if (j&(1<<x)) res[s][j]=2*x+1;
else res[s][j]=2*x+2;
}
}
}
}
//cout<<"size "<<res.size()<<"\n";
return res;
}
