#include "prison.h"
#include "prison.h"
//
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define sortv(vv) sort(vv.begin(), vv.end())
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long
using namespace std;
const int maxn=500+10,LOG=17, mod=1e9+7;
int block = 320, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define bt(i) (1 << (i))
//#define int ll
const int inf=1e9+10;
#define y1 yy
#define prev pre
#define pii pair <int, int>
int n;
pii getlr(int x, int iter)
{
int l = 3;
int r = n - 2;
forn(1, i, iter)
{
int m1 = l + (r - l + 1) / 3;
int m2 = m1 + (r - l + 1) / 3 + ((r - l + 1) % 3 == 2);
if(x < m1)
{
r = m1 - 1;
}
else if(x >= m1 && x < m2)
{
l = m1;
r = m2 - 1;
}
else
{
l = m2;
}
}
return {l, r};
}
vector<vector<int> > devise_strategy(int N) {
//19 20 21
vector <vector <int> > ans;
n = N;
int x = 20;
ans.assign(x + 1, {});
forn(0, i, x) ans[i].assign(n + 1, 0);
ans[0][0] = 0;
forn(1, j, n)
{
if(j == 1)
{
ans[0][j] = -(ans[0][j] + 1);
continue;
}
if(j == n)
{
ans[0][j] = -((ans[0][j] ^ 1) + 1);
continue;
}
int m1 = 3 + (n - 4) / 3;
int m2 = m1 + (n - 4) / 3 + ((n - 4) % 3 == 2);
if(j < m1)
ans[0][j] = 1;
else if(j >= m1 && j < m2)
ans[0][j] = 2;
else
ans[0][j] = 3;
}
forn(1, i, 18)
{
if((i - 1) / 3 % 2 == 0)
ans[i][0] = 1;
else
ans[i][0] = 0;
}
forn(1, i, 18)
{
forn(1, j, n)
{
if(j == 1)
{
ans[i][j] = -(ans[i][0] + 1);
continue;
}
if(j == n)
{
ans[i][j] = -((ans[i][0] ^ 1) + 1);
continue;
}
// cout << i << " " << j << endl;
pii otr = getlr(j, (i - 1) / 3);
if(j <= otr.f)
{
ans[i][j] = -(ans[i][0] + 1);
continue;
}
if(j >= otr.s)
{
ans[i][j] = -((ans[i][0] ^ 1) + 1);
continue;
}
int part2 = (i - 1) % 3 + 1;
int part1;
int m1 = otr.f + (otr.s - otr.f + 1) / 3;
int m2 = m1 + (otr.s - otr.f + 1) / 3 + ((otr.s - otr.f + 1) % 3 == 2);
if(j < m1)
{
part1 = 1;
}
else if(m1 <= j && j < m2)
{
part1 = 2;
}
else
{
part1 = 3;
}
if(part1 < part2) ans[i][j] = -(ans[i][0] + 1);
else if(part1 > part2) ans[i][j] = -((ans[i][0] ^ 1) + 1);
else if(part1 == part2)
{
otr = getlr(j, (i - 1) / 3 + 1);
if(otr.s - otr.f + 1 >= 7 || (i - 1) / 3 * 3 + 3 <= 15)
{
m1 = otr.f + (otr.s - otr.f + 1) / 3;
m2 = m1 + (otr.s - otr.f + 1) / 3 + ((otr.s - otr.f + 1) % 3 == 2);
if(j < m1) ans[i][j] = (i - 1) / 3 * 3 + 3 + 1;
else if(m1 <= j && j < m2) ans[i][j] = (i - 1) / 3 * 3 + 3 + 2;
else ans[i][j] = min(x, (i - 1) / 3 * 3 + 3 + 3);
}
else
{
if(otr.f == j)
{
ans[i][j] = -(ans[i][0] + 1);
continue;
}
if(otr.s == j)
{
ans[i][j] = -((ans[i][0] ^ 1) + 1);
continue;
}
if(otr.s - otr.f + 1 >= 4)
{
//11 12 13 14 15 16 17
if(j <= (otr.f + otr.s) / 2)
{
ans[i][j] = 19;
}
else
{
ans[i][j] = 20;
}
}
else
{
if(otr.s - otr.f + 1 == 3)
{
ans[i][j] = 19;
}
}
}
}
}
}
ans[19][0] = (ans[18][0] ^ 1);
ans[20][0] = ans[19][0];
forn(1, j, n)
{
pii otr = getlr(j, 6);
if(otr.s - otr.f + 1 >= 4)
{
int l = otr.f + 1;
int r = (otr.f + otr.s) / 2;
if(j <= l) ans[19][j] = -(ans[19][0] + 1);
if(j >= r) ans[19][j] = -((ans[19][0] ^ 1) + 1);
l = (otr.f + otr.s) / 2 + 1;
r = otr.s - 1;
if(j <= l) ans[20][j] = -(ans[20][0] + 1);
if(j >= r) ans[20][j] = -((ans[20][0] ^ 1) + 1);
}
else
{
if(j == otr.f)
ans[19][j] = -(ans[19][0] + 1);
if(j == otr.s)
ans[19][j] = -((ans[19][0] ^ 1) + 1);
}
}
return ans;
}
