#include "prison.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define vout(x) for(auto u : x)cout<<u<<' ';cout<<'\n';
using namespace std;
const vi divv = {3,3,3,3,3,2,2,1};
const vi ad = {1,4,7,10,13,16,19,20};
const vi chec = {0,1,1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,1,1,0};
vector<vi>v(21);
void solve(int l, int r, int layer, int dex){
if(divv[layer] == 3){
for(int j = ad[layer]; j<=ad[layer] + 2; j++){
if(j > dex){
for(int i = l; i<=r; i++){
if(layer % 2 == 0){
v[j][i] = -2;
}
else v[j][i] = -1;
}
}
else if(j < dex){
for(int i = l; i<=r; i++){
if(layer % 2 == 0){
v[j][i] = -1;
}
else v[j][i] = -2;
}
}
else{
if(divv[layer + 1] == 3){
int a = l + (r - l + 1) / 3;
int b = l + (r - l + 1) / 3 * 2;
for(int i = l; i<=r; i++){
if(i < a)v[j][i] = ad[layer + 1];
else if(i < b)v[j][i] = ad[layer + 1] + 1;
else v[j][i] = ad[layer + 1] + 2;
}
if(layer % 2 == 0){
v[j][l] = -2;
v[j][r] = -1;
}
else{
v[j][l] = -1;
v[j][r] = -2;
}
solve(l+1, a-1, layer + 1, ad[layer + 1]);
solve(a, b-1, layer + 1, ad[layer + 1] + 1);
solve(b, r-1, layer + 1, ad[layer + 1] + 2);
}
else{
int mid = (l + r) / 2;
for(int i = l; i<=r; i++){
if(i <= mid)v[j][i] = ad[layer + 1];
else v[j][i] = ad[layer + 1] + 1;
}
if(layer % 2 == 0){
v[j][l] = -2;
v[j][r] = -1;
}
else{
v[j][l] = -1;
v[j][r] = -2;
}
solve(l+1, mid, layer + 1, ad[layer + 1]);
solve(mid + 1, r-1, layer + 1, ad[layer + 1] + 1);
}
}
}
}
else if(divv[layer] == 2){
for(int j = ad[layer]; j<=ad[layer] + 1; j++){
if(j > dex){
for(int i = l; i<=r; i++){
if(layer % 2 == 0){
v[j][i] = -2;
}
else v[j][i] = -1;
}
}
else if(j < dex){
for(int i = l; i<=r; i++){
if(layer % 2 == 0){
v[j][i] = -1;
}
else v[j][i] = -2;
}
}
else{
if(divv[layer + 1] == 1){
for(int i = l; i<=r; i++){
v[j][i] = ad[layer + 1];
}
if(layer % 2 == 0){
v[j][l] = -2;
v[j][r] = -1;
}
else{
v[j][l] = -1;
v[j][r] = -2;
}
solve(l + 1, r - 1, layer + 1, ad[layer + 1]);
}
else{
int mid = (l + r) / 2;
for(int i = l; i<=r; i++){
if(i <= mid)v[j][i] = ad[layer + 1];
else v[j][i] = ad[layer + 1] + 1;
}
if(layer % 2 == 0){
v[j][l] = -2;
v[j][r] = -1;
}
else{
v[j][l] = -1;
v[j][r] = -2;
}
solve(l+1, mid, layer + 1, ad[layer + 1]);
solve(mid + 1, r-1, layer + 1, ad[layer + 1] + 1);
}
}
}
}
else{
if(l != r){
if(layer % 2 == 0){
v[dex][l] = -2;
v[dex][r] = -1;
}
else{
v[dex][l] = -1;
v[dex][r] = -2;
}
}
}
}
vi tern(int x){
int cur = 1;
vi ret;
while(x > 0){
ret.pb(x % (cur * 3) / cur);
x -= (x % (cur * 3));
cur *= 3;
}
while(ret.size() < 6)ret.pb(0);
reverse(ret.begin(), ret.end());
return ret;
}
std::vector<std::vector<int>> devise_strategy(int N) {
if(N <= 729){
vector<vi>v(19, vi(N+1));
v[0][0] = 0;
FOR(i, 1, N+1){
vi cur = tern(i);
v[0][i] = 1 + cur[0];
}
FOR(dig, 1, 7){
if(dig % 2 == 1){
v[dig * 3 - 2][0] = 1;
v[dig * 3 - 1][0] = 1;
v[dig * 3][0] = 1;
}
else{
v[dig * 3 - 2][0] = 0;
v[dig * 3 - 1][0] = 0;
v[dig * 3][0] = 0;
}
FOR(i, 1, N+1){
vi cur = tern(i);
f0r(j, 3){
if(cur[dig-1] < j){
v[(dig - 1) * 3 + 1 + j][i] = (dig % 2 == 1 ? -2 : -1);
}
else if(cur[dig-1] > j){
v[(dig - 1) * 3 + 1 + j][i] = (dig % 2 == 1 ? -1 : -2);
}
else{
if(dig != 6)v[(dig - 1) * 3 + 1 + j][i] = dig * 3 + 1 + cur[dig];
else v[(dig - 1) * 3 + 1 + j][i] = 1;
}
}
}
}
/*
f0r(i, 25){
f0r(j, 11)cout<<v[i][j]<<' ';
cout<<'\n';
}
*/
return v;
}
else{
f0r(i, 21)v[i].resize(N+1);
f0r(i, 21)v[i][0] = chec[i];
int a = N / 3;
int b = N / 3 * 2;
FOR(i, 1, N+1){
if(i < a)v[0][i] = 1;
else if(i < b)v[0][i] = 2;
else v[0][i] = 3;
}
v[0][1] = -1;
v[0][N] = -2;
solve(2, a-1, 0, 1);
solve(a, b-1, 0, 2);
solve(b, N-1, 0, 3);
f0r(i, 16){
FOR(j, 1, N){
if(v[i][j] == 0){
if(v[(i + 2) / 3 * 3 - 3][j] == -2)v[i][j] = -1;
else v[i][j] = -2;
}
}
}
FOR(i, 16, 20){
FOR(j, 1, N){
if(v[i][j] == 0){
if(v[(i + 1) / 2 * 2 - 2][j] == -2)v[i][j] = -1;
else v[i][j] = -2;
}
}
}
FOR(i, 20, 21){
FOR(j, 1, N){
if(v[i][j] == 0){
if(v[i-1][j] == -2)v[i][j] = -1;
else v[i][j] = -2;
}
}
}
/*
f0r(i, 21){
f0r(j, 20)cout<<v[i][j]<<' ';
cout<<'\n';
}
*/
return v;
}
}
