// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#include "richest.h"
using namespace std;
int solveSmall(int n){//task 1 is just a n^2 brute force
//simmilar to first explore task
//surely
	vector<int> x,y;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			x.push_back(i),y.push_back(j);
		}
	}
	vector<int> z=ask(x,y),cnt(n);//ask-2005 refrence 0-0
	for(auto&i:z){
		cnt[i]++;
		if(cnt[i]==n-1)return i;
	}
	return 0;
}
int solveLarge(int n,int s){//sqrt comparison
//solution is to split the entire thing up into sections
//find largest in each section then split it down
	vector<int>idx(n);
	for(int i=0;i<n;i++)
		idx[i]=i;
	vector<int>szs={(int)1e5,(int)25e4,(int)125e3,(int)625e2,(int)31250,(int)15625,(int)7813,(int)1};
	for(int U=0;U<8;U++){
		vector<vector<int>>asks(szs[U]);
		for(int i=0;i<n;i++){
			asks[i%szs[U]].push_back(idx[i]);
		}
		vector<int> x,y;
		for(int i=0;i<szs[U];i++)
			for(int j=0;j<asks[i].size();j++)
				for(int k=j+1;k<asks[i].size();k++)
					x.push_back(j),y.push_back(k);
		vector<int>z=ask(x,y),cnt(n);
		for(auto&i:z){
			cnt[i]++;
		}
		idx.resize(szs[U]);
		for(int i=0;i<szs[U];i++){
			idx[i]=-1;
			for(auto&j:asks[i]){
				if(cnt[j]==asks[i].size()-1){
					idx[i]=j;
				}
			}
		}
	}
	return idx[0];
}
int richest(int n, int t,int s){
	if(t==1)return solveSmall(n);
	return solveLarge(n,s);
}