#include "prison.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
#ifdef LOCAL
#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
#define eprintf(...) 42
#endif
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
clock_t startTime;
double getCurrentTime() {
return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
const int K = 44;
int n;
int seq[] = {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3};
int sum[] = {0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45};
int p[K + 1];
vector<vector<int>> ans;
int get_bit(int x, int k) {
for (int i = 8; i > k; i--) x /= seq[i];
return x % seq[k];
}
set<int> setik;
void build(int l, int r, int x) {
// if (setik.find(x) != setik.end()) assert(false);
// setik.insert(x);
if (l > r) return;
// printf("SEG %d %d = %d\n", l, r, x);
int his_bag = (p[x] % 2 == 1 ? 1 : 2);
int my_bag = (his_bag ^ 1 ^ 2);
ans[x][l] = -my_bag;
ans[x][r] = -his_bag;
for (int i = 1; i < l; i++)
ans[x][i] = -my_bag;
for (int i = r + 1; i <= n; i++)
ans[x][i] = -his_bag;
vector<int> pp[seq[p[x]]];
for (int i = l + 1; i < r; i++)
pp[get_bit(i, p[x])].push_back(i);
if (x == 0) {
for (int k = 0; k < seq[p[x]]; k++) {
if (pp[k].empty()) continue;
int L = pp[k][0], R = L;
for (int j : pp[k]) {
L = min(L, j);
R = max(R, j);
ans[x][j] = k + 1;
}
build(l, r, k + 1);
}
} else {
int L = 1e9, R = -1;
for (int i = l + 1; i < r; i++) {
int my_bit = get_bit(i, p[x] - 1);
int his_bit = x - sum[p[x] - 1] - 1;
if (my_bit != his_bit) {
ans[x][i] = (my_bit < his_bit ? -my_bag : -his_bag);
} else {
L = min(L, i);
R = max(R, i);
}
}
for (int j = L; j <= R; j++)
ans[x][j] = sum[p[x]] + get_bit(j, p[x]) + 1;
for (int i = 0; i < seq[p[x]]; i++) {
build(L, R, sum[p[x]] + i + 1);
}
}
}
vector<vector<int>> devise_strategy(int n) {
::n = n;
ans.resize(K);
for (int i = 0; i < K; i++)
ans[i].resize(n + 1);
for (int i = 1; i <= K; i++) {
p[i] = p[i - 1];
while(sum[p[i]] < i) p[i]++;
}
for (int i = 0; i < K; i++)
ans[i][0] = (p[i] & 1);
build(1, n, 0);
// for (int i = 0; i < K; i++) {
// for (int j = 0; j <= n; j++) {
// printf("%d ", ans[i][j]);
// }
// printf("\n \n");
// }
return ans;
}
