#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
//poziom 1 poziom 2 poziom 3 poziom 4 poziom 5 poziom 6 poziom 7 poziom 8
int poz[21];
vector<vector<int>> s(21);
vector<int> na_poziomie[10];
vector<pair<int,int>> przedzialy[10];
void obl(int gl, int a, int b, int jak){
if(a > b) return;
int x, y;
if(gl % 2 == 0){
x = -1;
y = -2;
}
else{
x = -2;
y = -1;
}
przedzialy[gl].push_back({a,b});
if(gl < 5){
int kt = na_poziomie[gl][jak - 1];
//cout << a << " " << b << " " << gl << "\n";
s[kt][b] = y;
s[kt][a] = x;
for(int i = na_poziomie[gl+1][0]; i <= 20; ++i){
if(poz[i] % 2 == 0){
s[i][a] = -1;
s[i][b] = -2;
}
else{
s[i][a] = -2;
s[i][b] = -1;
}
}
a++;
b--;
if(a > b) return;
int c = a + (b - a) / 3;
int d = b - (b - a) / 3;
if((b - a + 1) % 3 == 0){
d--;
}
if(a <= c){
for(int i = a; i <= c; ++i){
s[kt][i] = na_poziomie[gl + 1][0];
}
for(int i = gl + 1; i <= gl + 1; ++i){
int gdz = na_poziomie[gl + 1][0];
if(gdz == 0 or gdz > 20) continue;
for(int j = c + 1; j <= b; ++j){
s[gdz][j] = (i % 2 == 1 ? -1 : -2);
}
}
obl(gl + 1, a, c, 1);
}
if(c+1 <= d){
for(int i = c + 1; i <= d; ++i){
s[kt][i] = na_poziomie[gl + 1][1];
}
for(int i = gl + 1; i <= gl + 1; ++i){
int gdz = na_poziomie[gl + 1][1];
if(gdz == 0 or gdz > 20) continue;
for(int j = a; j <= c; ++j){
s[gdz][j] = ((i % 2 == 1) ? -2 : -1);
}
for(int j = d + 1; j <= b; ++j){
s[gdz][j] = (i % 2 == 1 ? -1 : -2);
}
}
obl(gl + 1, c + 1, d, 2);
}
if(d+1 <= b){
for(int i = d + 1; i <= b; ++i){
s[kt][i] = na_poziomie[gl + 1][2];
}
for(int i = gl + 1; i <= gl + 1; ++i){
int gdz = na_poziomie[gl + 1][2];
if(gdz == 0 or gdz > 20) continue;
for(int j = a; j <= d; ++j){
s[gdz][j] = ((i % 2 == 1) ? -2 : -1);
}
}
obl(gl + 1, d + 1, b, 3);
}
}
else{
int kt = na_poziomie[gl][jak - 1];
//cout << a << " " << b << " " << gl << " " << kt << "\n";
s[kt][b] = y;
s[kt][a] = x;
for(int i = na_poziomie[gl+1][0]; i <= 20; ++i){
//cout << i << " debug\n";
if(poz[i] % 2 == 0){
s[i][a] = -1;
s[i][b] = -2;
}
else{
s[i][a] = -2;
s[i][b] = -1;
}
}
a++;
b--;
if(a > b) return;
int c = a + (b - a) / 2;
if(b - a + 1 <= 2){
c = b;
}
//cout << a << " " << c << " " << b << "\n";
if(a <= c){
//cout << "%\n";
for(int i = a; i <= c; ++i){
s[kt][i] = na_poziomie[gl + 1][0];
}
for(int i = gl + 1; i <= gl + 1; ++i){
int gdz = na_poziomie[gl + 1][0];
if(gdz == 0 or gdz > 20) continue;
for(int j = c + 1; j <= b; ++j){
s[gdz][j] = (i % 2 == 1 ? -1 : -2);
}
}
obl(gl + 1, a, c, 1);
}
if(c + 1 <= b){
//cout << "^\n";
for(int i = c + 1; i <= b; ++i){
s[kt][i] = na_poziomie[gl + 1][1];
}
for(int i = gl + 1; i <= gl + 1; ++i){
int gdz = na_poziomie[gl + 1][1];
if(gdz == 0 or gdz > 20) continue;
for(int j = a; j <= c; ++j){
s[gdz][j] = (i % 2 == 1 ? -2 : -1);
}
}
obl(gl + 1, c + 1, b, 2);
}
}
return;
}
vector<vector<int>> devise_strategy(int n){
poz[0] = 0; poz[1] = poz[2] = poz[3] = 1; poz[4] = poz[5] = poz[6] = 2; poz[7] = poz[8] = poz[9] = 3;
poz[10] = poz[11] = poz[12] = 4; poz[13] = poz[14] = poz[15] = 5; poz[16] = poz[17] = 6; poz[18] = poz[19] = 7; poz[20] = 8;
for(int i = 0; i <= 20; ++i){
na_poziomie[poz[i]].push_back(i);
}
for(int i = 0; i <= 20; ++i){
s[i].resize(n + 1);
int poziom = poz[i];
s[i][0] = poziom % 2;
for(int j = 1; j <= n; ++j){
s[i][j] = -3;
}
}
for(int i = 0; i <= 9; ++i){
for(int j = 0; j < 2; ++j){
na_poziomie[i].push_back(50);
}
}
obl(0, 1, 5000, 1);
// for(int i = 0; i <= 20; ++i){
// cout << "i: " << (i <= 9 ? "0" : "") << i << " ";
// for(int j = 0; j <= n; ++j){
// cout << (s[i][j] >= 0 ? "+" : "") << s[i][j] << " ";
// }
// cout << "\n";
// }
// cout << "\n";
return s;
}
// bool spr(int a, int b){
// int gdz = 0;
// int d = 0;
// //cout << a << " " << b << "\n";
// for(int i = 0; i < 500; ++i){
// int kt = s[gdz][0];
// //cout << gdz << " " << kt << " gdzkt\n";
// int val;
// if(kt == 0){
// val = a;
// }
// else{
// val = b;
// }
// //cout << val << " val\n";
// //cout << s[gdz][val] << " nxt\n";
// if(s[gdz][val] == -1){
// if(a < b){
// d = 2;
// break;
// }
// else{
// d = 1;
// cout << a << " " << b << " " << "ZLA ODP" << "\n";
// break;
// }
// }
// else if(s[gdz][val] == -2){
// if(a > b){
// d = 2;
// break;
// }
// else{
// d = 1;
// cout << a << " " << b << " " << "ZLA ODP" << "\n";
// break;
// }
// }
// else if(s[gdz][val] == -3){
// cout << a << " " << b << " " << "PROSZE NIE" << "\n";
// d = 1;
// break;
// }
// else{
// gdz = s[gdz][val];
// }
// }
// if(d == 0){
// cout << a << " " << b << " " << "BRAK" << "\n";
// return false;
// }
// else if(d == 1){
// return false;
// }
// else{
// return true;
// }
// return false;
// }
// int main(){
// int x = 5000;
// devise_strategy(x);
// // for(int i = 0; i <= 5; ++i){
// // cout << przedzialy[i][0].first << " " << przedzialy[i][0].second << "\n";
// // }
// // cout << "\n";
// // for(int i = 1; i <= x; ++i){
// // for(int j = 1; j <= x; ++j){
// // if(i == j) continue;
// // if(spr(i, j) == false){
// // cout << i << " " << j << " ZLE\n";
// // return 0;
// // }
// // }
// // }
// return 0;
// }
