#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[5000];
vector<int> synowie[5000];
int dokogo[5001][30];
int ktorysyn[5001];
int kiedyodpowiedz[5001];
void policz(int v, int poziom, int a, int b){
przedzial[v] = {a,b};
for (int i = a; i <= b; i++) dokogo[i][poziom] = v;
//if (a <= 3800 && 3800 <= b) cout<<v<<" # "<<a<<" "<<b<<"\n";
if (poziom < 200){
for (int j = poziom; j < 30; j++) dokogo[a][j] = dokogo[b][j] = v;
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--;
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){
vector<vector<int> > tab(22);
for (int liczba = 0; liczba < 22; liczba++){
int poziom = (liczba+2)/3;
int ktory = 0;
if (liczba != 0){
ktory = (liczba-1)%3;
}
tab[liczba].resize(N);
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 == 3800 && liczba == 2){
cout<<wierzcholek<<" "<<ktorysyn[wierzcholek]<<" "<<ktory<<"\n";
}*/
if (ktorysyn[wierzcholek] != ktory){
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{
tab[liczba][worek] = 1+3*poziom;
if (synowie[wierzcholek].size() > 1){
auto przedzial1 = przedzial[synowie[wierzcholek][1]];
if (przedzial1.first <= worek) tab[liczba][worek]++;
}
if (synowie[wierzcholek].size() > 2){
auto przedzial2 = przedzial[synowie[wierzcholek][2]];
if (przedzial2.first <= worek) tab[liczba][worek]++;
}
}
}
}
return tab;
}
/*int main(){
//ios_base::sync_with_stdio(0);
//cin.tie(0);
int i;
policz(++pt,0,1,5000);
for (i = 1; i <= 5000; i++){
cout<<i<<" # ";
for (int j = 0; j <= 7; j++) cout<<dokogo[i][j]<<" ";
cout<<"\n";
}
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;
}*/
