#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
const int N=5005;
int n;
vector<vector<int>> s;
int mx;
int calc(int l,int r,int pos){
int sz=(r-l+3)/3;
return (pos-l)/sz;
}
pair<int,int> get(int l,int r,int num){
int sz=(r-l+3)/3;
int nl=l+sz*num;
int nr=l+sz*(num+1)-1;
return {max(l,min(nl,r)),max(l,min(nr,r))};
}
void solve(array<int,2> l,array<int,2> r,int id,int cur,int d){
if(l[cur]>=r[cur])return;
set<tuple<array<int,2>,array<int,2>,int,int,int>> st;
for(int x=0;x<3;x++){
s[id][0]=cur;
for(int j=l[cur];j<=r[cur];j++){
int val=calc(l[cur],r[cur],j);
if(val==x){
auto [nl,nr]=get(l[cur],r[cur],x);
if(j==nl){
s[id][j]=-cur-1;
}else if(j==nr){
s[id][j]=cur-2;
}else{
int val2=calc(nl+1,nr-1,j);
s[id][j]=d+3+val2;
array<int,2> tl={nl,nl},tr={nr,nr};
tl[cur]++;
tr[cur]--;
st.emplace(tl,tr,d+3+val2,cur^1,d+3);
}
}else if(val>x){
s[id][j]=cur-2;
}else{
s[id][j]=-cur-1;
}
}
id++;
}
mx=max(mx,id);
for(auto [a,b,c,d,e]:st)solve(a,b,c,d,e);
}
vector<vector<int>> devise_strategy(int _n){
n=_n;
vector<int> pw(8);
pw[0]=1;
for(int i=1;i<9;i++)pw[i]=pw[i-1]*3;
s=vector<vector<int>>(100,vector<int>(n+1));
s[0][0]=0;
for(int j=1;j<=n;j++){
int val=calc(1,n,j);
s[0][j]=val+1;
}
solve({1,1},{n,n},1,1,1);
s.resize(mx);
s.pop_back();
s.pop_back();
return s;
}
