#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=5007;
ll n,m,k;
ll pw[N];
int ind=0;
void comp_result(vector<vector<int>>&ans, int cur){
// cur = (k+1)*step+rem
// rem=0 -> A
// rem!=0 -> B, A_(rem-1)
int mnac=cur%(k+1);
if(mnac==0){
ans[cur][0]=0;
}
else{
ans[cur][0]=1;
// mnac-1 -> the group of the bag A
}
int tmp=cur;
cur/=(k+1); // the current step (k^(ind-cur))
// ind-cur>=1 (don't need more), => cur<=ind-1 => num<=(k+1)*(ind-1)
for(int i=1;i<=n;i++){
int vl=i;
vl%=pw[ind-cur+1];
vl/=pw[ind-cur];
if(mnac!=0){
if(vl<mnac-1){
ans[tmp][i]=-2;
}
else if(vl>mnac-1){
ans[tmp][i]=-1;
}
else{
ans[tmp][i]=(k+1)*(cur+1);
}
}
else{
int res=(k+1)*cur+vl+1;
ans[tmp][i]=res;
}
// cout<<ans[tmp][i]<<" ";
if(ans[tmp][i]==(k+1)*(ind+1))ans[tmp][i]=0;
// if(ans[tmp][i]>(k+1)*(ind+1))cout<<tmp<<" "<<i<<": "<<ans[tmp][i]<<endl;
}
// cout<<endl;
}
vector<vector<int>> devise_strategy(int NN) {
n=NN;
k=3;
pw[0]=1;
while(pw[ind]<=n){
ind++;
pw[ind]=pw[ind-1]*k;
}
ind--;
// cout<<ind<<endl;
vector<vector<int>>ans((k+1)*(ind+1),vector<int>(n+1,0));
for(int i=0;i<(k+1)*(ind+1);i++){
comp_result(ans,i);
}
return ans;
}
