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

#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

#ifdef DEBUG
auto& operator<<(auto& os, const pair<auto,auto> &p) {
	return os<<"("<<p.first<<", "<<p.second<<")";
}

auto& operator<<(auto& os, const auto &v) {
	os<<"{";
	for(auto it=begin(v);it!=v.end();++it) {
		if(it!=begin(v)) os<<", ";
		os<<(*it);
	}
	return os<<"}";
}

void dbg_out(auto... x) {
	((cerr<<' '<<x), ...) << endl;
}

#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif



vi solve_k(vector<int> index, int K) {
	dbg(index);
	int n = sz(index);
	vector<pii> q;

	auto query_k = [&](int ind, int k) {
		rep(i,0,k)
			rep(j,i+1,k)
				q.emplace_back(ind + i, ind + j);
	};

	for(int i=0;i<n;i+=K)
		query_k(i, min(K, n-i));

	vi a, b;
	for(auto [x, y] : q) {
		a.push_back(index[x]);
		b.push_back(index[y]);
	}

	dbg(a, b);

	vi res = ask(a, b);
	dbg(res);

	auto get_num = [](int k) {
		return k * (k - 1) / 2;
	};

	vi new_index;

	auto get_best = [&](int ind, int ind_res, int k) {
		int number = get_num(k);
		rep(i,0,k) {
			int num = 0;
			rep(j,0,number)
				num += index[ind + i] == res[ind_res + j]; 
			if(num == k-1) {
				new_index.push_back(index[ind + i]);
				break;
			}
		}
	};

	for(int i=0;i<n;i+=K) {
		int start = get_num(K) * (i / K);
		get_best(i, start, min(K, n-i));
	}
	dbg(new_index);
	return new_index;
}

int richest(int N, int T, int S) {
	if(T == 1) {
		vi a, b;
		rep(i,0,N) rep(j,i+1,N) {
			a.push_back(i);
			b.push_back(j);
		}
		auto res = ask(a, b);
		sort(all(res));
		int prev = -1;
		int num = 0;
		for(auto x : res) {
			if(x == prev) {
				num++;
				if(num == N-1) return x;
			}
			else {
				prev = x;
				num = 1;
			}
		}
		assert(false);
	}
    vi perm(N);
    iota(all(perm), 0);

    const vi v = {2, 2, 2, 2, 3, 6, 19, 183};
    int product = 1;
    for(auto x : v)
    	product *= x;
    assert(product >= 1000000);

    for(const auto x : v) {
    	perm = solve_k(perm, x);
    	if(sz(perm) == 1) return perm[0];
    }

    return -1;
}

// n * (k-1) / 2
// 1099944

// 2: n / 2 -> n / 2
// 2: n / 4 -> n / 4
// 2: n / 8 -> n / 8
// 3: n / 8 -> n / 24

// SUM: n