#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
const int MAX_BIT = 12;
int cnt = 0, id[13][2];
ii rev[25];
int getBit(int x, int k) {
return (x >> k) & 1;
}
vector<vector<int>> devise_strategy(int N) {
vector<int> V;
for (int i = 1; i <= MAX_BIT; i++)
for (int j = 0; j <= 1; j++) {
id[i][j] = ++cnt;
rev[cnt] = {i, j};
}
vector<vector<int>> rs(cnt + 1, vector<int>(N + 1));
for (int i = 1; i <= N; i++)
rs[0][i] = id[MAX_BIT][getBit(i, MAX_BIT)];
for (int i = 1; i <= cnt; i++) {
int bit = rev[i].first, val = rev[i].second;
rs[i][0] = 1 - (MAX_BIT - bit) % 2;
for (int j = 1; j <= N; j++) {
if (getBit(j, bit) < val)
rs[i][j] = (rs[i][0] ? -2 : -1);
else if (getBit(j, bit) > val)
rs[i][j] = (rs[i][0] ? -1 : -2);
else {
if (bit == 1) {
if (!getBit(j, 0))
rs[i][j] = (rs[i][0] ? -2 : -1);
else
rs[i][j] = (rs[i][0] ? -1 : -2);
} else
rs[i][j] = id[bit - 1][getBit(j, bit - 1)];
}
}
}
return rs;
}
/********************************************************************/
//static constexpr int kNumPrisoners = 500;
//
//static void invalid_strategy(string message) {
// printf("%s\n", message.c_str());
// exit(0);
//}
//
//int main() {
// freopen("../_input", "r", stdin);
// int N;
// assert(1 == scanf("%d", &N));
//
// vector<vector<int>> strategy = devise_strategy(N);
// if (strategy.size() == 0) {
// invalid_strategy("s is an empty array");
// }
// int x = strategy.size() - 1;
// for (int i = 0; i <= x; ++i) {
// if (static_cast<int>(strategy[i].size()) != N + 1) {
// invalid_strategy("s[i] contains incorrect length");
// }
// if (strategy[i][0] < 0 || strategy[i][0] > 1) {
// invalid_strategy("First element of s[i] is non-binary");
// }
// for (int j = 1; j <= N; ++j) {
// if (strategy[i][j] < -2 || strategy[i][j] > x) {
// invalid_strategy("s[i][j] contains incorrect value");
// }
// }
// }
//
// FILE *log_file = fopen("log.txt", "w");
//
// int A, B;
// while (1 == scanf("%d", &A) && A != -1) {
// assert(1 == scanf("%d", &B));
// bool answer = false;
// int whiteboard = 0;
// for (int i = 0; i < kNumPrisoners && !answer; ++i) {
// int check = strategy[whiteboard][0];
// whiteboard = strategy[whiteboard][check == 0 ? A : B];
// if (whiteboard < 0) {
// answer = true;
// printf("%c\n", "BA"[whiteboard + 2]);
// } else {
// if (i > 0) {
// fprintf(log_file, " ");
// }
// fprintf(log_file, "%d\n", whiteboard);
// fprintf(log_file, " (%d, %d)\n", rev[whiteboard].first, rev[whiteboard].second);
// }
// }
// if (!answer) {
// printf("X\n");
// }
// fprintf(log_file, "\n");
// fflush(log_file);
// }
//}
