#include <bits/stdc++.h>
#include "prison.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 5000 + 7;
int pos[N];
vector<int> bas = {2, 3, 3, 3, 3, 2, 2, 2}, gs;
int Do(int n)
{
int xd = 1, s = 1;
gs.pb(1);
for(int i = 0; i < (int)bas.size() && xd < n; ++i)
{
gs.pb(bas[i]);
xd *= bas[i];
//xd += 2;
s += bas[i];
}
gs.pb(1);
return s;
}
vector<vector<int>> devise_strategy(int _N)
{
int n = _N, il;
il = Do(n);
for(int i = 1; i <= n; ++i) pos[i] = i - 1;
pos[0] = -1; pos[n + 1] = -2;
vector<int> bas(n + 1, -1);
vector<vector<int>> ans(il, bas);
int s = 0, r = 0, xd = n;
for(int i = 1; i < (int)gs.size(); ++i)
{
//cerr << i << " " << gs[i] << "\n";
for(int j = s; j <= s + gs[i - 1] - 1; ++j)
ans[j][0] = r;
//int d = (xd + (gs[i - 1] - 1)) / gs[i - 1];
int d = xd;
int nd = (xd - 2 + (gs[i] - 1)) / gs[i];
for(int j = 1; j <= n; ++j)
{
//cerr << pos[j] << " ";
if(pos[j] == -1)
for(int l = 0; l < gs[i - 1]; ++l)
ans[s + l][j] = (-1 - r);
if(pos[j] == -2)
for(int l = 0; l < gs[i - 1]; ++l)
ans[s + l][j] = (-2 + r);
if(pos[j] < 0) continue;
int x = pos[j] / d;
for(int l = 0; l < x; ++l)
ans[s + l][j] = (-2 + r);
for(int l = x + 1; l < gs[i - 1]; ++l)
ans[s + l][j] = (-1 - r);
if(pos[j] > 0) pos[j] %= d;
if(pos[j] >= 0)
--pos[j];
if(pos[j] == d - 2 || pos[j + 1] < 0) pos[j] = -2;
if(pos[j] == -1)
ans[s + x][j] = (-1 - r);
if(pos[j] == -2)
ans[s + x][j] = (-2 + r);
if(pos[j] >= 0)
ans[s + x][j] = s + gs[i - 1] + (pos[j] / nd);
}
//cerr << "\n";
s += gs[i - 1];
r ^= 1;
xd = (xd - 2 + gs[i] - 1) / gs[i];
}
/*cerr << ans.size() << "\n";
for(int i = 0; i < (int)ans.size(); ++i)
{
for(int j = 0; j < (int)ans[i].size(); ++j)
cerr << ans[i][j] << " ";
cerr << "\n";
}*/
return ans;
}
