#include "prison.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
mt19937 rng(123);
#define ld long double
#define ull unsigned long long
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(a) a.begin(), a.end()
#define ff first
#define ss second
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define setp(x) setprecision(x)
int old(int n){
int k = 31 - __builtin_clz(n);
if(__builtin_popcount(n) == 1) k--;
return k;
}
#define a -1
#define b -2
vector<vector<int>> devise_strategy(int n) {
vector<vi> res;
if(n == 2){
return {{0,a,b}};
}
int n2 = old(n);
res.assign((n2 + 1)*2+1, vi((1<<(n2 + 1)) + 1,0));
int x = res.size(), sz = res[0].size();
for(int i = 1; i < sz; i ++){
if((i-1) & (1 << n2)) res[0][i] = 2;
else res[0][i] = 1;
// cout << res[0][i] << endl;
}
int l = 3, r = 4;
for(int i = 1; i < x; i +=2){
if(i%4 == 1) res[i][0] = res[i + 1][0] = 1;
if(res[i][0] == 1){
// cout << i << ' ' << i+1 << endl;
for(int j = 1; j < sz; j ++){
if((j-1)&(1 << n2)){
res[i][j] = a;
if((j-1)&(1 << (n2 - 1))){
res[i + 1][j] = r;
}else res[i + 1][j] = l;
}else{
res[i + 1][j] = b;
if((j-1)&(1 << (n2 - 1))){
res[i][j] = r;
}else res[i][j] = l;
}
}
}else{
for(int j = 1; j < sz; j ++){
if((j-1)&(1 << n2)){
res[i][j] = b;
if((j-1)&(1 << (n2 - 1))){
res[i + 1][j] = r;
}else res[i + 1][j] = l;
}else{
res[i + 1][j] = a;
if((j-1)&(1 << ( n2 - 1))){
res[i][j] = r;
}else res[i][j] = l;
}
}
}
l += 2; r += 2;
n2 --;
}
vector<vi> ans(x - 2, vi(n + 1, -10));
for(int i = 0; i < x - 4; i ++){
for(int j = 0; j <= n; j ++){
ans[i][j] = res[i][j];
}
}
r -= 2, l -= 2;
for(int j = x - 4; j < x - 2; j ++){
ans[j][0] = res[j][0];
for(int i = 1; i <= n; i ++){
if(res[j][i] > 0){
if(i%2 == 1){
ans[j][i] = (res[j][0] == 0? a : b);
}else{
ans[j][i] = (res[j][0] == 0? b : a);
}
}else ans[j][i] = res[j][i];
}
}
/* for(int i = 0; i < x; i ++){
for(int j = 0; j < sz; j ++){
if(res[i][j] >= 0) cout << res[i][j] << ' ';
else cout << char(-res[i][j] + 'a' - 1) << ' ';
} cout << endl;
}*/
return ans;
}
