#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n;
int p3[10];
vector<vector<signed>> devise_strategy(signed N){
n=N;
p3[2]=8;
rep(x,3,10) p3[x]=p3[x-1]*3;
vector<vector<signed> > res;
rep(x,0,22){
vector<signed> temp;
if (x==0){
temp.pub(0);
rep(x,1,n+1) temp.pub(1+x/p3[7]%3);
}
else if (x==19){ //[1,2,3]
temp.pub(1);
rep(x,1,n+1){
int res=x%8;
if (res<=1) temp.pub(-2);
else if (3<=res) temp.pub(-1);
else temp.pub(21);
}
}
else if (x==20){ //[4,5,6]
temp.pub(1);
rep(x,1,n+1){
int res=x%8;
if (res<=4) temp.pub(-2);
else if (6<=res) temp.pub(-1);
else temp.pub(21);
}
}
else if (x==21){
temp.pub(0);
rep(x,1,n+1){
int res=x%8;
if (res==1 || res==4) temp.pub(-1);
else if (res==3 || res==6) temp.pub(-2);
else temp.pub(0);
}
}
else{
int layer=7-(x-1)/3;
int residue=(x-1)%3;
int nxt=(8-layer)*3+1;
int layerp=layer%2;
temp.pub(layerp);
//cout<<x<<" "<<layer<<" "<<temp[0]<<endl;
//cout<<p3[layer-1]<<" "<<p3[layer]<<endl;
rep(x,1,n+1){
int res2=x/p3[layer]%3;
if (res2<residue) temp.pub(~(layerp));
else if (res2>residue) temp.pub(~(layerp^1));
else{
if (layer==2){
int res1=x%8;
if (res1==0) temp.pub(~(layerp));
else if (res1==7) temp.pub(~(layerp^1));
else if (res1<=3) temp.pub(19);
else temp.pub(20);
}
else{
int res1=x/p3[layer-1]%3;
temp.pub(nxt+res1);
}
}
}
}
res.pub(temp);
}
return res;
}
