/* AM+DG */
/*
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)
// #define DEBUG
const int CHOOSE_A = 0, CHOOSE_B = 1;
const int GUESS_A = -1, GUESS_B = -2;
void make_strat(const vi& dp, const vi& opt_divider, vvi& s, int bag_to_choose, int l, int r, int x, int next_avail) {
int n = r - l + 1;
s[x][0] = bag_to_choose;
s[x][l] = (bag_to_choose == CHOOSE_A ? GUESS_A : GUESS_B);
s[x][r] = (bag_to_choose == CHOOSE_A ? GUESS_B : GUESS_A);
// ! TODO once you recurse, also update the strategy for the sublevels
if(n > 2) {
// Assume it's going to be perfectly divided (N = 5588 guarantees it anyways)
int divisions = opt_divider[n];
vi sizes_pref(divisions + 1, l + 1);
LI(i, 0, divisions) {
sizes_pref[i + 1] = sizes_pref[i] + (n - 2) / divisions;
}
LI(i, 0, divisions) {
int divl = sizes_pref[i], divr = sizes_pref[i + 1] - 1;
LI(j, l, divl) {
s[next_avail + i][j] = (bag_to_choose == CHOOSE_A ? GUESS_B : GUESS_A);
}
LI(j, divr + 1, r + 1) {
s[next_avail + i][j] = (bag_to_choose == CHOOSE_A ? GUESS_A : GUESS_B);
}
make_strat(dp, opt_divider, s, 1 - bag_to_choose, divl, divr, next_avail + i, next_avail + divisions);
}
}
}
vvi devise_strategy(int N) {
// DP
int maxn = 5588;
vi dp(maxn + 1, INF(int));
vi opt_divider(maxn + 1, 0);
dp[0] = 0;
dp[1] = 0;
dp[2] = 0;
LI(i, 3, maxn + 1) {
dp[i] = dp[(i - 2 - 1) / 3 + 1] + 3;
opt_divider[i] = 3;
if(dp[(i - 2 - 1) / 2 + 1] + 2 <= dp[i]) opt_divider[i] = 2;
dp[i] = min(dp[i], dp[(i - 2 - 1) / 2 + 1] + 2);
if(dp[i - 2] + 1 <= dp[i]) opt_divider[i] = 1;
dp[i] = min(dp[i], dp[i - 2] + 1);
}
LI(i, 0, maxn + 1) {
cout << i << " " << dp[i] << " " << opt_divider[i] << endl;
}
// Strat building
vvi s;
for(int i = 0; i <= 20; i++) {
vi sr(maxn + 1, 0);
s.pb(sr);
}
make_strat(dp, opt_divider, s, CHOOSE_A, 1, maxn, 0, 1);
for(int i = 0; i <= 20; i++) {
LI(j, 0, maxn - N) s[i].pop_back(); // Keep popping until the array is of the correct size
}
return s;
}
#ifdef DEBUG
int main() {
int N;
cin >> N;
vvi s = devise_strategy(N);
LI(x, 0, 21) {
cout << x << " " << s[x][0] << endl;
}
return 0;
}
#endif
