#include <bits/stdc++.h>
#include "prison.h"
using namespace std;
using ll = long long;
vector<vector<int>> devise_strategy(int n) {
vector<vector<int>> ans(25, vector<int>(n + 1));
ans[0][0] = 0;
for (int i = 1;i <= n;i++) {
if ((i >> 12) & 1) ans[0][i] = 1;
else ans[0][i] = 13;
}
for (int i = 1;i <= 11;i++) {
ans[i][0] = ans[i + 12][0] = i & 1;
int b = 13 - i;
for (int j = 1;j <= n;j++) {
if ((j >> b) & 1) {
if (ans[i][0]) ans[i + 12][j] = -1;
else ans[i + 12][j] = -2;
if ((j >> (b - 1)) & 1) {
ans[i][j] = i + 1;
}
else {
ans[i][j] = 12 + i + 1;
}
}
else {
if (ans[i][0]) ans[i][j] = -2;
else ans[i][j] = -1;
if ((j >> (b - 1)) & 1) {
ans[i + 12][j] = i + 1;
}
else {
ans[i + 12][j] = 12 + i + 1;
}
}
}
}
ans[12][0] = ans[24][0] = 0;
for (int j = 1;j <= n;j++) {
if ((j >> 1) & 1) {
ans[24][j] = -2;
if (j & 1) {
ans[12][j] = -2;
}
else {
ans[12][j] = -1;
}
}
else {
ans[12][j] = -1;
if (j & 1) {
ans[24][j] = -2;
}
else {
ans[24][j] = -1;
}
}
}
return ans;
}
// int main() {
// int n = 5000, a, b;
// vector<vector<int>> adj = devise_strategy(n);
// for (int i = 1;i <= 5000;i++) {
// for (int j = 1;j <= 5000;j++) {
// if (i == j) continue;
// int now = 0;
// int cnt = 0;
// while (now >= 0 && cnt <= 500) {
// if (adj[now][0] == 0) {
// now = adj[now][i];
// }
// else {
// now = adj[now][j];
// }
// cnt++;
// }
// if (i < j && now == -2) {
// cout << i << ' ' << j << '\n';
// }
// else if (i > j && now == -1) {
// cout << i << ' ' << j << '\n';
// }
// }
// }
// // int i = a, j = b;
// // int now = 0;
// // int cnt = 0;
// // while (now >= 0 && cnt <= 500) {
// // cout << now << ' ';
// // if (adj[now][0] == 0) {
// // now = adj[now][i];
// // }
// // else {
// // now = adj[now][j];
// // }
// // cnt++;
// // }
// // cout << now << ' ';
// }
