#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<long double, long double>
#define pld pair<ld, ld>
#define NEK 200000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001
using namespace std;
int daj(int a, int ktore) {
if (ktore < 0) return 0;
while (ktore) {
a /= 3;
ktore--;
}
a %= 3;
return a;
}
int umocni(int a, int b) {
int vys = 1;
while (b) {
if ((b % 2) == 1) {
vys *= a;
}
a *= a;
b /= 2;
}
return vys;
}
vec<vec<int>> devise_strategy(int n) {
int log = 0;
while (umocni(3, log) <= n) log++;
int x = log + log * 2;
vec<vec<int>> s(x + 1, vec<int>(n + 1));
s[0][0] = 0;
int hod0 = 1 - ((log - 1) % 2);
for (int i = 1; i <= n; i++) {
s[0][i] = (log-1) + log * (daj(i, log - 1)) + 1;
}
ffor(i, 1, x + 1) {
int mi = i - 1;
if (((mi % log) % 2) == hod0) {
s[i][0] = 0;
}
else {
s[i][0] = 1;
}
for (int j = 1; j <= n; j++) {
int ktore = mi % log;
int hod = mi / log;
int jeho_hod = daj(j, ktore);
if (jeho_hod > hod) {
if (s[i][0] == 0) {
s[i][j] = -2;
}
else {
s[i][j] = -1;
}
}
if (jeho_hod < hod) {
if (s[i][0] == 0) {
s[i][j] = -1;
}
else {
s[i][j] = -2;
}
}
if (jeho_hod == hod) {
ktore--;
hod = daj(j, ktore);
s[i][j] = ktore + log * hod + 1;
}
}
}
return s;
/*
int x = 32;
vec<vec<int>> s(x + 1, vec<int>(n+1));
s[0][0] = 0;
for (int j = 1; j < n; j++) {
s[0][j] = 8 * daj(j, 0) + 1;
}
ffor(i, 1, x + 1) {
s[i][0] = 1 - (i % 2);
for (int j = 1; j < n; j++) {
//na tabuly je napisane i, ja som v krabici videl j
int ktore = (i-1) % 8;
int kolko = ((i-1) / 8) % 8;
int hod = daj(j, ktore);
if (hod == kolko) {
s[i][j] = (ktore + 1) + 8 * daj(j, ktore + 1) + 1;
}
else {
if (hod > kolko) {
s[i][j] = (-1) * (1 + s[i][0]) + 1;
}
if (hod < kolko) {
s[i][j] = (-1) * (2 - s[i][0]) + 1;
}
}
}
}
return s;*/
}
int krokuj(vec<vec<int>>& s, int x, int a, int b) {
//cout << x << endl;
if (x < 0) {
return x;
}
int k;
if (s[x][0] == 0) {
//cout << 'A' << endl;
k = a;
}
else {
//cout << 'B' << endl;
k = b;
}
return krokuj(s, s[x][k], a, b);
}
/*signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//cin >> n;
while (1) {
int n;
//n = rand() % 500 + 2;
cin >> n;
int a = 0, b = 0;
cin >> a >> b;
//while (a == b) {
// a = rand() % n + 1;
// b = rand() % n + 1;
// }
vec<vec<int>> s = devise_strategy(n);
int odp = krokuj(s, 0, a, b);
cout << odp << '\n';
if (odp == -1 && (a > b)) {
int lol = 1;
cout << n << ' ' << a << ' ' << b << endl;
return 0;
}
if (odp == -2 && (b > a)) {
int lol = 1;
cout << n << ' ' << a << ' ' << b << endl;
return 0;
}
}
return 0;
}*/
