#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 = 39;
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};
int p[40];
vector<vector<int>> ans;
int get_bit(int x, int k) {
for (int i = 12; i > k; i--) x /= seq[i];
return x % seq[k];
}
void build(int l, int r, int x) {
// 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;
vector<int> pp[seq[p[x]]];
for (int i = l + 1; i < r; i++)
pp[get_bit(i, p[x])].push_back(i);
// printf("wtf!\n");
for (int i = 1; i <= l; i++) ans[x][i] = -my_bag;
for (int i = r; i < ans[0].size(); i++) ans[x][i] = -his_bag;
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 bit = (x - sum[p[x] - 1]) - 1;
for (int k = 0; k < bit; k++)
for (int j : pp[k])
ans[x][j] = -my_bag;
for (int k = bit + 1; k < seq[p[x]]; k++)
for (int j : pp[k])
ans[x][j] = -his_bag;
if (!pp[bit].empty()) {
map<int, vector<int>> go;
for (int j : pp[bit]) {
ans[x][j] = sum[p[x]] + get_bit(j, p[x] + 1) + 1;
go[ans[x][j]].push_back(j);
}
for (auto& p : go) {
int L = p.second[0], R = L;
for (int j : p.second) {
L = min(L, j);
R = max(R, j);
}
build(L, R, p.first);
}
}
}
}
vector<vector<int>> devise_strategy(int 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;
}
