#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<std::vector<int>> devise_strategy(int N) {
// vector<int> powers = {4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1};
// vector<vector<int>> res = {{0}};
// for (int i = 0; i < powers[0] && res[0].size() <= N; ++i) res[0].push_back(1);
// for (int i = 0; i < powers[0] && res[0].size() <= N; ++i) res[0].push_back(2);
// for (int i = 0; i < powers.size(); ++i) {
// for (int j = 0; j < 2; ++j) {
// vector<int> cur = {(i + 1) % 2};
// int curNext = i * 2 + 3;
// int bagRet = -1;
// if ((i + 1) % 2) bagRet = -2;
// for (int k = 0; k < N; ++k) {
// int val = k;
// for (int p = 0; p < i; ++p) {
// int power = powers[p];
// if (val >= power) val -= power;
// }
// int curDiv = powers[i];
// if (val < curDiv && j) cur.push_back(bagRet);
// else if (val >= curDiv && !j) cur.push_back(-3 - bagRet);
// else {
// if (i < powers.size() - 1) {
// if (val >= curDiv) val -= curDiv;
// curDiv = powers[i + 1];
// if (val < curDiv) cur.push_back(curNext);
// else cur.push_back(curNext + 1);
// } else cur.push_back(0);
// }
// }
// res.push_back(cur);
// }
// }
vector<int> powers = {2187, 729, 243, 81, 27, 9, 3, 1};
vector<vector<int>> res = {{0}};
for (int i = 0; i < powers[0] && res[0].size() <= N; ++i) res[0].push_back(1);
for (int i = 0; i < powers[0] && res[0].size() <= N; ++i) res[0].push_back(2);
for (int i = 0; i < powers[0] && res[0].size() <= N; ++i) res[0].push_back(3);
for (int i = 0; i < powers.size(); ++i) {
for (int j = 0; j < 3; ++j) {
vector<int> cur = {(i + 1) % 2};
int curNext = i * 3 + 4;
int bagRet = -1;
if ((i + 1) % 2) bagRet = -2;
for (int k = 0; k < N; ++k) {
int val = k;
for (int p = 0; p < i; ++p) {
int power = powers[p];
while (val >= power) val -= power;
}
int curDiv = powers[i];
int valDiv = val / curDiv;
if (valDiv < j) cur.push_back(bagRet);
else if (valDiv > j) cur.push_back(-3 - bagRet);
else {
if (i < powers.size() - 1) {
while (val >= curDiv) val -= curDiv;
curDiv = powers[i + 1];
valDiv = val / curDiv;
cur.push_back(curNext + valDiv);
} else cur.push_back(0);
}
}
res.push_back(cur);
}
}
// int cnt = 0;
// for (auto &i : res) {
// cout << cnt++ << ' ';
// for (auto &j : i) cout << j << ' ';
// cout << endl;
// }
return res;
}
