#include "prison.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
const int p = 3;
vector<vector<int>> devise_strategy(int n) {
int b = 8, last = 0;
vector<vector<int>> res;
vector<int> v(n + 1);
vector<vector<int>> bit(n + 1, vector<int>(b + 1));
for(int i=1;i<=n;i++){
int x = i;
for(int j=0;j<=b;j++){
bit[i][j] = x % p;
x /= p;
}
}
int is = 0, nxt = 4, cur = 0;
while(~b){
res.push_back(v);
if(!last){
last++;
res[last - 1][0] = 0;
for(int j=1;j<=n;j++){
res[last - 1][j] = last + bit[j][b];
}
} else {
if(!b){
if(is){
for(int j=1;j<=n;j++){
assert(bit[j][b] != 1);
if(bit[j][b] == 0) res[last][j] = -1;
else res[last][j] = -2;
}
} else {
res[last][0] = 1;
for(int j=1;j<=n;j++){
assert(bit[j][b] != 1);
if(bit[j][b] == 0) res[last][j] = -2;
else res[last][j] = -1;
}
}
break;
}
if(is){
res[last][0] = 0;
for(int j=1;j<=n;j++){
if(bit[j][b] == cur){
if(b == 1){
if(bit[j][b - 1] == 0) res[last][j] = -1;
if(bit[j][b - 1] == 2) res[last][j] = -2;
if(bit[j][b - 1] == 1) res[last][j] = nxt;
} else if(b > 0) res[last][j] = nxt + bit[j][b - 1];
} else {
if(bit[j][b] > cur){
res[last][j] = -2;
} else {
res[last][j] = -1;
}
}
}
if(last % 3 == 0){
b--;
is ^= 1;
nxt += 3;
}
cur = (cur + 1) % 3;
last++;
} else {
res[last][0] = 1;
for(int j=1;j<=n;j++){
if(bit[j][b] == cur){
if(b == 1){
if(bit[j][b - 1] == 0) res[last][j] = -2;
if(bit[j][b - 1] == 2) res[last][j] = -1;
if(bit[j][b - 1] == 1) res[last][j] = nxt;
} else if(b > 0) res[last][j] = nxt + bit[j][b - 1];
} else {
if(bit[j][b] > cur){
res[last][j] = -1;
} else {
res[last][j] = -2;
}
}
}
if(last % 3 == 0){
b--;
is ^= 1;
nxt += 3;
}
cur = (cur + 1) % 3;
last++;
}
}
}
//~ for(auto v : res){
//~ for(auto x : v) cout<<x<<" ";
//~ cout<<endl;
//~ } cout<<endl;
//~ for(int j=0;j<last;j++){
//~ for(int i=0;i<=n;i++) cout<<res[j][i]<<" ";
//~ } cout<<"\n";
return res;
}
