#include "richest.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e6 + 5;
const int M = 1005;

vector <int> vec, tv[N << 2], op[3], a, b;

bitset <M> vis;

int tot, ans[N];

inline int solve1(vector <int> vec) {
	a.clear(), b.clear();
	int n = vec.size();
	for (int i = 0; i < n; ++i) {
		vis[i] = true;
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < i; ++j) {
			a.emplace_back(vec[i]);
			b.emplace_back(vec[j]);
		}
	}
	vector <int> res = ask(a, b);
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < i; ++j) {
			if (res[cnt] == vec[i]) {
				vis[j] = false;
			} else {
				vis[i] = false;
			}
			++cnt;
		}
	}
	for (int i = 0; i < n; ++i) {
		if (vis[i]) {
			return vec[i];
		}
	}
	return -1;
}

inline void solve2(vector <int> pos) {
	a.clear(), b.clear();
	for (auto x: pos) {
		int n = tv[x].size();
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < i; ++j) {
				a.emplace_back(tv[x][i]);
				b.emplace_back(tv[x][j]);
			}
		}
	}
	vector <int> res = ask(a, b);
	int cnt = 0;
	for (auto x: pos) {
		int n = tv[x].size();
		for (int i = 0; i < n; ++i) {
			vis[i] = true;
		}
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < i; ++j) {
				if (res[cnt] == tv[x][i]) {
					vis[j] = false;
				} else {
					vis[i] = false;
				}
				++cnt;
			}
		}
		for (int i = 0; i < n; ++i) {
			if (vis[i]) {
				ans[x] = tv[x][i];
				break;
			}
		}
	}
}

inline vector <int> f(vector <int> vec) {
	a.clear(), b.clear();
	int n = vec.size();
	for (int i = 0; i < (n >> 1); ++i) {
		a.emplace_back(vec[i << 1]);
		b.emplace_back(vec[i << 1 | 1]);
	}
	return ask(a, b);
}

inline int solve(vector <int> vec) {
	int id = ++tot;
	op[2].emplace_back(id);
	tv[id] = vec;
	return id;
}

inline int solve18(vector <int> vec) {
	int n = 18, id = ++tot;
	tv[id].clear();
	op[1].emplace_back(id);
	vector <int> tmp;
	for (int i = 0; i < n; ++i) {
		tmp.emplace_back(vec[i]);
		if ((i + 1) % 3 == 0) {
			tv[id].emplace_back(solve(tmp));
			tmp.clear();
		}
	}
	return id;
}

inline int solve22(vector <int> vec) {
	int n = 22, id = ++tot;
	tv[id].clear();
	op[1].emplace_back(id);
	vector <int> tmp;
	for (int i = 0; i < n; ++i) {
		tmp.emplace_back(vec[i]);
		if (i < 16 && (i + 1) % 3 == 0) {
			tv[id].emplace_back(solve(tmp));
			tmp.clear();
		}
		if (i == 18 || i == 21) {
			tv[id].emplace_back(solve(tmp));
			tmp.clear();
		}
	}
	return id;
}

inline int solve324(vector <int> vec) {
	int n = 324, id = ++tot;
	tv[id].clear();
	op[0].emplace_back(id);
	vector <int> tmp;
	for (int i = 0; i < n; ++i) {
		tmp.emplace_back(vec[i]);
		if ((i + 1) % 18 == 0) {
			tv[id].emplace_back(solve18(tmp));
			tmp.clear();
		}
	}
	return id;
}

inline int solve342(vector <int> vec) {
	int n = 342, id = ++tot;
	tv[id].clear();
	op[0].emplace_back(id);
	vector <int> tmp;
	for (int i = 0; i < n; ++i) {
		tmp.emplace_back(vec[i]);
		if ((i + 1) % 18 == 0) {
			tv[id].emplace_back(solve18(tmp));
			tmp.clear();
		}
	}
	return id;
}

inline int solve346(vector <int> vec) {
	int n = 346, id = ++tot;
	tv[id].clear();
	op[0].emplace_back(id);
	vector <int> tmp;
	for (int i = 0; i < n; ++i) {
		tmp.emplace_back(vec[i]);
		if (i <= 323 && (i + 1) % 18 == 0) {
			tv[id].emplace_back(solve18(tmp));
			tmp.clear();
		}
		if (i == 345) {
			tv[id].emplace_back(solve22(tmp));
			tmp.clear();
		}
	}
	return id;
}

inline void solve62500(vector <int> vec) {
	int n = 62500, id = ++tot;
	tv[id].clear();
	vector <int> tmp;
	for (int i = 0; i < n; ++i) {
		tmp.emplace_back(vec[i]);
		if (i < 60875 && (i + 1) % 342 == 0) {
			tv[id].emplace_back(solve342(tmp));
			tmp.clear();
		}
		if (i == 60879) {
			tv[id].emplace_back(solve346(tmp));
			tmp.clear();
		}
		if (i + 1 > 60880 && (i - 60879) % 324 == 0) {
			tv[id].emplace_back(solve324(tmp));
			tmp.clear();
		}
	}
}

int richest(int n, int t, int s) {
	vec.clear();
	for (int i = 0; i < n; ++i) {
		vec.emplace_back(i);
	}
	if (t == 1) {
		return solve1(vec);
	}
	for (int i = 0; i < 4; ++i) {
		vec = f(vec);
	}
	tot = 0;
	op[0].clear(), op[1].clear(), op[2].clear();
	solve62500(vec);
	solve2(op[2]);
	for (auto x: op[1]) {
		for (auto &y: tv[x]) {
			y = ans[y];
		}
	}
	solve2(op[1]);
	for (auto x: op[0]) {
		for (auto &y: tv[x]) {
			y = ans[y];
		}
	}
	solve2(op[0]);
	for (auto &y: tv[1]) {
		y = ans[y];
	}
	return solve1(tv[1]);
}