#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> devise_strategy(int size_limit)
{
const int MAXN = 5000;
const vector<int> counts = {2, 3, 3, 3, 3, 2, 2, 2};
const vector<int> levels = {5000, 2499, 833, 277, 92, 30, 14, 6, 2};
const int depth = counts.size();
auto transform = [&](int x, int stage)
{
for (int i = 1; i <= stage; ++i)
{
if (x <= 1)
return 1;
x = (x - 2) % levels[i] + 1;
}
return x;
};
vector<vector<int>> strat;
vector<int> base(MAXN + 1);
base[0] = 0;
for (int i = 1; i <= MAXN; ++i)
{
int v = transform(i, 0);
if (v == 1)
base[i] = -1;
else if (v == levels[0])
base[i] = -2;
else
base[i] = (v - 2) / levels[1] + 1;
}
strat.push_back(base);
for (int stage = 0; stage < depth; ++stage)
{
int turn = (stage & 1) ^ 1;
int win = turn == 0 ? -1 : -2;
int lose = -3 - win;
int offset = strat.size() + counts[stage];
for (int opp = 0; opp < counts[stage]; ++opp)
{
vector<int> row(MAXN + 1);
row[0] = turn;
for (int i = 1; i <= MAXN; ++i)
{
int val = transform(i, stage);
if (val == 1)
{
row[i] = win;
}
else if (val == levels[stage])
{
row[i] = lose;
}
else
{
int id = (val - 2) / levels[stage + 1];
if (id < opp)
row[i] = win;
else if (id > opp)
row[i] = lose;
else
{
int next = transform(i, stage + 1);
if (next == 1)
row[i] = win;
else if (next == levels[stage + 1])
row[i] = lose;
else
{
if (stage + 2 > depth)
{
row[i] = -1;
}
else
{
int next_id = (next - 2) / levels[stage + 2];
row[i] = next_id + offset;
}
}
}
}
}
strat.push_back(row);
}
}
for (auto &row : strat)
{
row.resize(size_limit + 1);
for (int &x : row)
x = clamp(x, -2, (int)strat.size() - 1);
}
return strat;
}
