#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 all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long
using namespace std;
const int maxn=1e5+100,LOG=20,mod=998244353;
int block = 106, 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=2e9;
#define y1 yy
#define prev pre
#define pii pair <int, int>
int n;
pii getlr(int i, int iter)
{
int l = 1;
int r = n;
forn(1, it, iter)
{
l++;
r--;
int m1 = l + (r - l + 1) / 3;
int m2 = m1 + (r - l + 1) / 3 + ((r - l + 1) % 3 == 2);
if(l <= i && i < m1) r = m1-1;
else if(m1 <= i && i < m2)
{
l = m1;
r = m2 - 1;
}
else l = m2;
}
return {l, r};
}
pii getm(pii i)
{
int m1 = i.f + (i.s - i.f + 1) / 3;
int m2 = m1 + (i.s - i.f + 1) / 3 + ((i.s - i.f + 1) % 3 == 2);
return {m1, m2};
}
vector <vector <int> > devise_strategy(int N)
{
n = N;
vector <vector <int> > ans;
int x = 20;
ans.assign(x + 1, {});
forn(0, i, x)
{
ans[i].assign(n + 1, 0);
}
ans[0][0] = 0;
ans[0][1] = -1;
ans[0][n] = -2;
forn(2, i, n - 1)
{
pii lr = getm({2, n - 1});
if(i < lr.f)
ans[0][i] = 1;
else if(lr.f <= i && i < lr.s)
ans[0][i] = 2;
else
ans[0][i] = 3;
}
forn(1, i, x)
{
ans[i][0] = ((i - 1) / 3 + 1) % 2;
}
forn(1, i, 18)
{
forn(1, j, n)
{
pii lr = getlr(j, (i - 1) / 3);
lr.f++;
lr.s--;
pii m = getm(lr);
int num1 = (i - 1) % 3 + 1;
if(j <= lr.f)
{
ans[i][j] = -((ans[i][0] + 1));
continue;
}
if(j >= lr.s)
{
ans[i][j] = -((ans[i][0] ^ 1) + 1);
continue;
}
int num2;
if(j < m.f) num2 = 1;
else if(m.f <= j && j < m.s) num2 = 2;
else num2 = 3;
if(num2 < num1) ans[i][j] = -((ans[i][0]) + 1);
else if(num2 > num1) ans[i][j] = -((ans[i][0] ^ 1) + 1);
else
{
pii otr = getlr(j, (i - 1) / 3 + 1);
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;
}
otr.f++;
otr.s--;
if(i >= 16)
{
int mid = (otr.f + otr.s) / 2;
if(j <= mid)
ans[i][j] = 19;
else
ans[i][j] = 20;
continue;
}
m = getm(otr);
if(j < m.f) ans[i][j] = ((i - 1) / 3 + 1) * 3 + 1;
else if(m.f <= j && j < m.s) ans[i][j] = ((i-1)/3+1)*3+2;
else ans[i][j] = ((i-1)/3*3+1)*3+3;
}
}
}
forn(1, j, n)
{
pii otr = getlr(j, 6);
if(j <= otr.f)
{
ans[19][j] = -(ans[19][0] + 1);
ans[20][j] = -(ans[20][0] + 1);
continue;
}
if(j >= otr.s)
{
ans[19][j] = -((ans[19][0] ^ 1) + 1);
ans[20][j] = -((ans[20][0] ^ 1) + 1);
continue;
}
otr.f++;
otr.s--;
int mid = (otr.f + otr.s) / 2;
if(j > mid) ans[19][j] = -((ans[19][0] ^ 1) + 1);
else
if(j == otr.f) ans[19][j] = -(ans[19][0] + 1);
if(j <= mid) ans[20][j] = -(ans[20][0] + 1);
else
if(j == otr.s) ans[20][j] = -((ans[20][0] ^ 1) + 1);
}
return ans;
}
