#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 = 13; // 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;
for (int i = 0; i < CT; i++) {
vector<vi> vec(3, vi(MAX + 1, 0));
vi cuts;
for (int j = 0; j <= (1 << (i + 1)); j++) {
cuts.pb(MAX * j / (1 << (i + 1)));
}
/* cout<<"cuts: ";
for (int x : cuts)
cout<<x<<" ";
cout<<endl;*/
int S = cuts.size(); // pow of 2 plus 1
// number 3 * i
vec[0][0] = 0;
for (int j = 0; j < S - 1; j += 2) {
for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
vec[0][k] = 3 * i + 1;
}
}
for (int j = 1; j < S - 1; j += 2) {
for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
vec[0][k] = 3 * i + 2;
}
}
// number 3 * i + 1
vec[1][0] = 1;
for (int j = 0; j < S - 1; j += 2) {
for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
vec[1][k] = 3 * i + 3;
}
}
for (int j = 1; j < S - 1; j += 2) {
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 += 2) {
for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
vec[2][k] = -2;
}
}
for (int j = 1; j < S - 1; j += 2) {
for (int k = cuts[j] + 1; k <= cuts[j + 1]; k++) {
vec[2][k] = 3 * i + 3;
}
}
for (vi v : vec)
ans.pb(v);
}
for (int i = 3 * CT - 3; i < 3 * CT; i++) {
for (int j = 0; j <= MAX; j++) {
if (ans[i][j] == 3 * CT)
ans[i][j] = -1;
}
}
/* cout<<"ANSWER: "<<endl;
for (vi v : ans) {
for (int x : v)
cout<<x<<" ";
cout<<endl;
}*/
return ans;
}
// can make same for N = 5000, just truncate
