#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
#include "prison.h"
int CT = 10; // CHANGE TO 13 AFTER
vector<vi> devise_strategy(int N) {
int MAX = N;
// crop ans from MAX + 1 at the end
vi sz; // size is 13
int curr = MAX;
while (curr > 1) {
curr = (curr + 1) / 2;
sz.pb(curr);
}
vector<vi> ans;
int base = 1;
for (int i = 0; i < CT; i++) {
vector<vi> vec(4, vi(MAX + 1, 0));
base *= 3;
vi cuts;
for (int j = 0; j <= base; j++) {
cuts.pb(MAX * j / base);
}
/* cout<<"cuts: ";
for (int x : cuts)
cout<<x<<" ";
cout<<endl;*/
int S = cuts.size(); // pow of 3 plus 1
// number 3 * i
vec[0][0] = 0;
for (int j = 0; j < S - 1; j += 3) {
for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
vec[0][k] = 4 * i + 1;
}
}
for (int j = 1; j < S - 1; j += 3) {
for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
vec[0][k] = 4 * i + 2;
}
}
for (int j = 2; j < S - 1; j += 3) {
for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
vec[0][k] = 4 * i + 3;
}
}
// number 3 * i + 1
vec[1][0] = 1;
for (int j = 0; j < S - 1; j += 3) {
for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
vec[1][k] = 4 * i + 4;
}
}
for (int j = 1; j < S - 1; j += 3) {
for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
vec[1][k] = -1;
}
}
for (int j = 2; j < S - 1; j += 3) {
for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
vec[1][k] = -1;
}
}
// number 3 * i + 2
vec[2][0] = 1;
for (int j = 0; j < S - 1; j += 3) {
for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
vec[2][k] = -2;
}
}
for (int j = 1; j < S - 1; j += 3) {
for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
vec[2][k] = 4 * i + 4;
}
}
for (int j = 2; j < S - 1; j += 3) {
for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
vec[2][k] = -1;
}
}
// number 3 * i + 3
vec[3][0] = 1;
for (int j = 0; j < S - 1; j += 3) {
for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
vec[3][k] = -2;
}
}
for (int j = 1; j < S - 1; j += 3) {
for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
vec[3][k] = -2;
}
}
for (int j = 2; j < S - 1; j += 3) {
for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
vec[3][k] = 4 * i + 4;
}
}
for (vi v : vec)
ans.pb(v);
}
for (int i = 4 * CT - 4; i < 4 * CT; i++) {
for (int j = 0; j <= MAX; j++) {
if (ans[i][j] == 4 * CT)
ans[i][j] = -1;
}
}
/* cout<<"ANSWER: "<<endl;
for (vi v : ans) {
for (int x : v)
cout<<x<<" ";
cout<<endl;
}*/
return ans;
}
