#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//Autor: Michał Szeliga
#ifdef LOCAL
#define debug(...) __VA_ARGS__;
#else
#define debug(...) {}
#endif
#define read(...) debug((void)!freopen(__VA_ARGS__,"r",stdin););
int pt = 0;
pair<int,int> przedzial[5001];
vector<int> synowie[5001];
int dokogo[5001][30];
int ktorysyn[5001];
int kiedyodpowiedz[5001];
bool koniec[5001][30];
void policz(int v, int poziom, int a, int b){
przedzial[v] = {a,b};
//cout<<v<<" "<<a<<" "<<b<<"\n";
for (int i = a; i <= b; i++) dokogo[i][poziom] = v;
for (int j = poziom+1; j < 30; j++){
dokogo[a][j] = dokogo[b][j] = v;
koniec[a][j] = koniec[b][j] = 1;
}
//if (a <= 11 && 11 <= b) cout<<v<<" # "<<" "<<poziom<<": "<<a<<" "<<b<<"\n";
if (poziom < 5){
a++;b--;
if (a > b) return;
int c = a+(b-a)/3;
int d = b-(b-a)/3;
if (a <= c){
synowie[v].push_back(++pt);
ktorysyn[pt] = 0;
policz(pt,poziom+1,a,c);
}
if (c+1 <= d){
synowie[v].push_back(++pt);
ktorysyn[pt] = 1;
policz(pt,poziom+1,c+1,d);
}
if (d+1 <= b){
synowie[v].push_back(++pt);
ktorysyn[pt] = 2;
policz(pt,poziom+1,d+1,b);
}
}else{
a++;
b--;
if (a > b) return;
int c = (a+b)/2;
if (a <= c){
synowie[v].push_back(++pt);
policz(pt,poziom+1,a,c);
}
if (c+1 <= b){
synowie[v].push_back(++pt);
policz(pt,poziom+1,c+1,b);
}
}
}
vector<vector<int> > devise_strategy(int N){
policz(++pt,0,1,5000);
vector<vector<int> > tab(22);
vector<int> jakipoziom(22);
vector<int> ktoryziomek(22);
jakipoziom[0] = ktoryziomek[0] = 0;
for (int i = 0; i < 5; i++){
for (int j = 0; j < 3; j++){
jakipoziom[1+i*3+j] = i+1;
ktoryziomek[1+i*3+j] = j;
}
}
for (int i = 0; i < 3; i++){
for (int j = 0; j < 2; j++){
jakipoziom[16+i*2+j] = i+6;
ktoryziomek[16+i*2+j] = j;
}
}
for (int liczba = 0; liczba < 22; liczba++){
int poziom = jakipoziom[liczba];
int ktory = ktoryziomek[liczba];
tab[liczba].resize(N+1);
tab[liczba][0] = poziom%2;
int Moj = -1;
int Niemoj = -2;
if (poziom%2){
Moj = -2;
Niemoj = -1;
}
for (int worek = 1; worek <= N; worek++){
int wierzcholek = dokogo[worek][poziom];
int a = przedzial[wierzcholek].first;
int b = przedzial[wierzcholek].second;
/*if (worek == 3){
cout<<liczba<<" ### "<<"poziom: "<<poziom<<" "<<wierzcholek<<" "<<ktorysyn[wierzcholek]<<" "<<ktory<<"\n";
}*/
if (ktorysyn[wierzcholek] != ktory && !koniec[worek][poziom]){
if (ktorysyn[wierzcholek] < ktory) tab[liczba][worek] = Moj;
else tab[liczba][worek] = Niemoj;
}else if (worek == a){
tab[liczba][worek] = Moj;
}else if (worek == b){
tab[liczba][worek] = Niemoj;
}else{
int nowaliczba = liczba;
while (jakipoziom[nowaliczba] == jakipoziom[liczba]) nowaliczba++;
/* if (worek == 10 && liczba == 16){
cout<<"Amongas\n";
}*/
tab[liczba][worek] = nowaliczba;
if (synowie[wierzcholek].size() > 1){
auto przedzial1 = przedzial[synowie[wierzcholek][1]];
/*if (worek == 10 && liczba == 16){
cout<<przedzial1.first<<" ";
}*/
if (przedzial1.first <= worek) tab[liczba][worek]++;
}
if (synowie[wierzcholek].size() > 2){
auto przedzial2 = przedzial[synowie[wierzcholek][2]];
/*if (worek == 10 && liczba == 16){
cout<<przedzial2.first<<" ";
}*/
if (przedzial2.first <= worek) tab[liczba][worek]++;
}
/*if (worek == 10 && liczba == 16){
cout<<"\n";
}*/
}
/*if (worek == 3){
cout<<liczba<<" "<<tab[liczba][worek]<<"\n";
}*/
}
}
return tab;
}
/*int main(){
//ios_base::sync_with_stdio(0);
//cin.tie(0);
int i;
vector<vector<int> > strategia = devise_strategy(5000);
int N,A,B;
cin>>N>>A>>B;
int tablica = 0;
//return 0;
while (1){
int ruch = strategia[tablica][0];
int val = 0;
if (ruch == 0) val = A;
else val = B;
int ruch2 = strategia[tablica][val];
cout<<"Tab: "<<tablica<<" ktory: "<<ruch<<" val: "<<val<<" # "<<strategia[tablica][val]<<"\n";
tablica = strategia[tablica][val];
if (ruch2 < 0) exit(0);
}
return 0;
}*/
