#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > devise_strategy(int n){
vector<vector<int>> ans(21), ert(9), spec(9);
vector<int> szint(21, 0);
for (int i=0; i<=20; i++) {
ans[i].resize(n+1);
if (i<=8) ert[i].resize(n+1), spec[i].resize(n+1);
}
for (int i=0; i<=19; i++) {
szint[i]=(i+2)/3;
}
szint[20]=8;
for (int i=0; i<=20; i++) {
ans[i][0]=(szint[i]%2);
}
for (int j=1; j<=n; j++) {
int kis=1, nagy=5102;
for (int i=0; i<=8; i++) {
int res=0, res2=0;
if (j==26) {
//cout << "lepes " << kis << " " << nagy << "\n";
}
if (j==kis) res2=-1, res=1;
if (j==nagy) res2=-2, res=3;
if (kis<j && j<nagy) {
kis++, nagy--;
if (i<6) {
int k1=kis+(nagy+1-kis)/3, k2=2*k1-kis;
if (j<k1) res=1, nagy=k1-1;
else if (j<k2) res=2, kis=k1, nagy=k2-1;
else res=3, kis=k2;
}
if (i==6) res=19;
if (i==7) res=20;
if (i==8) res=0;
}
ert[i][j]=res, spec[i][j]=res2;
if (j==7 || j==8) {
//cout << "vege " << res << " " << res2 << "\n";
}
}
}
//cout << "vege " << ert[4][26] << "\n";
for (int i=0; i<=20; i++) {
for (int j=1; j<=n; j++) {
int ut=(1<=i && i<=18 ? (i-1)%3+1 : 0), b=ert[szint[i]][j], sp=spec[szint[i]][j], el=(1<=i && i<=18 ? ert[szint[i]-1][j] : 0);
if (ut!=el || sp) {
if (ut!=el) ans[i][j]=(el<ut ? -1 : -2);
else ans[i][j]=sp;
if (szint[i]%2) ans[i][j]=-3-ans[i][j];
/*if (i==13 && j==26) {
cout << "rossz " << b << " " << szint[i] << " " << ans[i][j] << "\n";
cout << ut << " " << b << " " << sp << "\n";
}*/
} else {
ans[i][j]=(i<16 ? i+(3-i%3)%3+b : b);
}
}
}
return ans;
}
void solve(vector<vector<int> > &sz, int a, int b) {
int pos=0, ans=0, lep=0;
while (lep<20 && ans==0) {
int kerd=(sz[pos][0]%2 ? b : a), kov=sz[pos][kerd];
//cout << "fontos " << pos << " " << kerd << " " << kov << "\n";
if (kov<0) {
ans=kov;
} else {
pos=kov, lep++;
}
}
if (lep>=20) {
cout << "vegtelen " << a << " " << b << "\n";
exit(0);
}
if (ans==-1 && a>b || ans==-2 && a<b) {
cout << "rossz valasz " << a << " " << b << "\n";
exit(0);
}
}
/*
int main()
{
int n=5000;
//cin >> n;
vector<vector<int> > sz=devise_strategy(n);
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (i!=j) {
solve(sz, i, j);
}
}
}
//solve(sz, 8, 7);
for (auto x:sz) {
cout << "sor " << cnt << ": ";
if (cnt<10) cout << " ";
cnt++;
for (auto y:x) {
if (0<=y && y<10) cout << " ";
cout << y << " ";
}
cout << "\n";
}
return 0;
}
*/
