// 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={1e5,25e4,125e3,625e2,31250,15625,7813,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);
}