#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > devise_strategy(int n){
vector<vector<int>> ans(21), ert(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);
}
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;
if (j==kis) res=-1;
if (j==nagy) res=-2;
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;
}
}
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];
if (b==-1 || b==-2 || (ut && b!=ut)) {
ans[i][j]=(b==-1 || b<ut ? -1 : -2);
if (szint[i]%2) ans[i][j]=-3-ans[i][j];
} else {
if (i<18) {
int s=(3-i%3)%3;
ans[i][j]=(i<18 ? i+s+b : b);
}
}
}
}
return ans;
}
/*int main()
{
ios_base::sync_with_stdio(false);
vector<vector<int> > sz=devise_strategy(20);
int cnt=0;
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;
}*/
