#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
vi po(9); //po[i]=3^i
int digit(int n, int pos){
return (n%po[pos+1]) / po[pos];
}
vector<vi> devise_strategy(int N) {
po[0]=1; FOR(i,1,9) po[i]=po[i-1]*3;
vector<vi> ans;
// i=0
vi ans0(N+1); FOR(i,1,N+1){
ans0[i]=1+digit(i,7);
}
ans.pb(ans0);
FOR(i,1,8){
FOR(j,0,3){
vi a(N+1);
a[0]=(i%2);
FOR(k,1,N+1){
int d = digit(k,8-i);
if (d<j){
// i%2 loses
a[k] = -1 -(i%2);
}
if (d==j){
int d2 = digit(k,7-i);
if (i==7){
if (d2==0) a[k]=-1-(i%2); //i%2 loses
if (d2==2) a[k]=(i%2)-2; //i%2 wins
if (d2==1) a[k]=22;
continue;
}
a[k] = 3*i + 1 + d2;
}
if (d>j){
// i%2 wins
a[k] = (i%2) - 2;
}
}
ans.pb(a);
}
}
ans0[0]=0;
FOR(i,1,N+1){
if (i%3==0){
ans0[i]=-1;
}
if (i%3==2){
ans0[i]=-2;
}
}
ans.pb(ans0);
return ans;
}
