#include "prison.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> devise_strategy(int n) {
int s = (int)sqrt(n) + 1;
int x = 3 * s;
vector<vector<int>> ans(x + 1, vector<int>(n + 1, 0));
ans[0][0] = 0;
for (int a = 1; a <= n; a++) ans[0][a] = (int)sqrt(a);
for (int k = 1; k < s; k++) {
ans[k][0] = 1;
for (int b = 1; b <= n; b++) {
int kb = (int)sqrt(b);
if (kb == k) ans[k][b] = s;
else ans[k][b] = (k < kb) ? -1 : -2;
}
}
ans[s][0] = 0;
for (int a = 1; a <= n; a++) {
int k = (int)sqrt(a);
int sq = k * k;
int r = a - sq;
ans[s][a] = s + 1 + r;
}
for (int st = s + 1; st <= x; st++) {
ans[st][0] = 1;
int ra = st - s - 1;
for (int b = 1; b <= n; b++) {
int k = (int)sqrt(b);
int sq = k * k;
int rb = b - sq;
ans[st][b] = (rb < ra) ? -2 : -1;
}
}
return ans;
}
