#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <queue>  
#include <map>
#include "richest.h"

using namespace std;
typedef long long ll;

int solve1(int n, int s) {
	vector<int> a, b;
	a.reserve(s);
	b.reserve(s);
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++) {
			a.push_back(i);
			b.push_back(j);
		}
	vector<int> c = ask(a, b);
	vector<vector<bool>> ds(n, vector<bool>(n));
	int P = 0;
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++) {
			ds[i][j] = (c[P++] == i);
			ds[j][i] = !ds[i][j];
		}
	for (int i = 0; i < n; i++) {
		bool ok = true;
		for (int j = 0; j < n; j++)
			if (j != i && !ds[i][j])
				ok = false;
		if (ok)
			return i;
	}
	return -1;
}

int richest(int n, int t, int s) {
	if (t == 1)
		return solve1(n, s);
	vector<int> can(n);
	for (int i = 0; i < n; i++)
		can[i] = i;
	while (can.size() > 1) {
		vector<int> a(can.size() / 2);
		vector<int> b(can.size() / 2);
		for (int i = 0; i * 2 + 1 < can.size(); i++) {
			a[i] = can[i * 2];
			b[i] = can[i * 2 + 1];
		}
		int d = -1;
		if (can.size() % 2)
			d = can.back();
		can = ask(a, b);
		if (d != -1)
			can.push_back(d);
	}
	return can[0];
}