#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
using namespace std;
template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
vector<int> bits[5005];
int bitMax[25];
void makeBits2(int l, int r)
{
int lx = l + 1, rx = r - 1;
int m = (lx + rx) / 2;
for (int i = l; i <= r; i++)
{
if (i == l)
{
bits[i].push_back(-1);
continue;
}
if (i == r)
{
bits[i].push_back(-2);
continue;
}
if (i <= m)
bits[i].push_back(0);
else
bits[i].push_back(1);
}
if (lx <= m)
makeBits2(lx, m);
if (m + 1 <= rx)
makeBits2(m + 1, rx);
}
void makeBits(int l, int r)
{
if (l > r)
return;
if (r - l + 1 <= 8)
{
makeBits2(l, r);
return;
}
int lx = l + 1, rx = r - 1;
int sub = (rx - lx + 2) / 3;
int m1 = lx + sub;
int m2 = lx + sub * 2;
// lx ~ m1, m1 + 1 ~ m2, m2 + 1 ~ rx
for (int i = l; i <= r; i++)
{
if (i == l)
{
bits[i].push_back(-1);
continue;
}
if (i == r)
{
bits[i].push_back(-2);
continue;
}
if (i <= m1)
bits[i].push_back(0);
else if (i <= m2)
bits[i].push_back(1);
else
bits[i].push_back(2);
}
if (lx > rx)
return;
makeBits(lx, m1);
makeBits(m1 + 1, m2);
makeBits(m2 + 1, rx);
}
int maxBit = 0;
void process(vector<vector<int>>& res, int n, int turn, int bit, int st)
{
if (bit == maxBit)
return;
int nxt = st;
for (int pre = 0; pre < bitMax[bit - 1]; pre++)
{
res.push_back(vector<int>(n + 1, 0));
res.back()[0] = turn;
nxt++;
}
int me = -(turn + 1);
int other = -((turn + 1) % 2 + 1);
for (int i = 1; i <= n; i++)
{
if (bits[i].size() <= bit - 1)
continue;
for (int pre = 0; pre < bitMax[bit - 1]; pre++)
{
if (bits[i][bit - 1] == -1)
res[st + pre][i] = me;
else if (bits[i][bit - 1] == -2)
res[st + pre][i] = other;
else if (bits[i][bit - 1] < pre)
res[st + pre][i] = me;
else if (bits[i][bit - 1] > pre)
res[st + pre][i] = other;
else
{
if (bits[i].size() <= bit)
continue;
if (bits[i][bit] == -1)
res[st + pre][i] = me;
else if (bits[i][bit] == -2)
res[st + pre][i] = other;
else
res[st + pre][i] = nxt + bits[i][bit];
}
}
}
process(res, n, (turn + 1) % 2, bit + 1, nxt);
}
vector<vector<int>> devise_strategy(int N)
{
vector<vector<int>> res;
makeBits(1, N);
for (int i = 1; i <= N; i++)
maxBit = max(maxBit, (int)bits[i].size());
for (int bit = 0; bit < maxBit; bit++)
{
for (int i = 1; i <= N; i++)
{
if (bits[i].size() <= bit)
continue;
bitMax[bit] = max(bitMax[bit], bits[i][bit] + 1);
}
}
res.push_back(vector<int>(N + 1, 0));
for (int i = 1; i <= N; i++)
{
if (bits[i][0] == -1)
res[0][i] = -1;
else if (bits[i][0] == 0)
res[0][i] = 1;
else if (bits[i][0] == 1)
res[0][i] = 2;
else if (bits[i][0] == 2)
res[0][i] = 3;
else
res[0][i] = -2;
}
process(res, N, 1, 1, 1);
return res;
}
