#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>
lli n,bolsa,act,mitad,w;
vector< vector<int> > res;
vector<int> trash;
vector<pll> rangos,mover;
lli escribe(lli b) {
b *= (-1);
b -= 1;
return b;
}
std::vector<std::vector<int>> devise_strategy(int N) {
// dividir (1,2) para pregutar por B y (3,4) para volver a preguntar por A
n = N;
res.push_back(trash);
res[0].resize(n+1);
res[0][0] = 0;
bolsa = 0;
w = (n+1)/2;
rep(i,2,n-1) {
if (i <= w) res[0][i] = 2; //abajo
else res[0][i] = 1; //arriba
}
res[0][1] = escribe(bolsa);
res[0][n] = escribe(bolsa^1);
rangos.push_back({2,n-1});
act = 1;
while (!rangos.empty()) {
bolsa ^= 1;
res.push_back(trash);
res[act].resize(n+1);
res.push_back(trash);
res[act+1].resize(n+1);
rep(pos,act,act+1) {
res[pos][0] = bolsa;
for(auto r : rangos) {
mitad = (r.second+r.first)/2;
rep(i,r.first,mitad) {// mitad de abajo
if (pos&1) res[pos][i] = escribe(bolsa);
else {
if (i == r.first) {res[pos][i] = escribe(bolsa); continue;}
if (i == mitad) {res[pos][i] = escribe(bolsa^1); continue;}
w = (r.first+mitad)/2;
if (i <= w) res[pos][i] = pos+2;
else res[pos][i] = pos+1;
}
}
rep(i,mitad+1,r.second) { //mitad de arriba
if (pos&1) {
if (i == mitad+1) {res[pos][i] = escribe(bolsa); continue;}
if (i == r.second) {res[pos][i] = escribe(bolsa^1); continue;}
w = (r.second + mitad + 1)/2;
if (i <= w) res[pos][i] = pos+3;
else res[pos][i] = pos+2;
}
else res[pos][i] = escribe(bolsa^1);
}
}
}
swap(mover,rangos);
rangos.clear();
for(auto m : mover) {
if (m.first == m.second) continue;
if (m.first + 1 == m.second) continue;
if (m.first + 2 == m.second) continue;
mitad = (m.first + m.second)/2;
rangos.push_back({m.first+1,mitad-1});
rangos.push_back({mitad+2,m.second-1});
}
act += 2;
}
act = res.size()-1;
rep(i,0,act) {
rep(j,1,n) {
if (res[i][j] > act) res[i][j] = -1;
}
}
return res;
}
// tener cuidado ya que la implementacion puede dejar valores mayores a x, eso es un wa (sube las x)
