#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;

int n;

void query(vector<int> &arr,vector<pair<int,int> > &e) {
	vector<int> x,y;
	for(auto i:e) x.push_back(i.first),y.push_back(i.second);
	vector<int> res=ask(x,y);
	static bool vis[N];
	memset(vis,0,sizeof(vis));
	for(int i=0;i<e.size();i++) {
		if(res[i]==x[i]) vis[y[i]]=1;
		else vis[x[i]]=1;
	}
	vector<int> arrr;
	for(int i:arr) if(!vis[i]) arrr.push_back(i);
	arr=arrr;
}

void solve1(int len,vector<int> &arr) {
	vector<pair<int,int> > e;
	int sz=arr.size();
	for(int i=0;i<sz;i+=len) {
		assert(i+len<=sz);
		for(int j=i;j<i+len;j++) for(int k=j+1;k<i+len;k++) e.push_back({arr[j],arr[k]});
	}
	query(arr,e);
}

void solve2(int len1,int cnt1,int len2,int cnt2,vector<int> &arr) {
	vector<pair<int,int> > e;
	int sz=arr.size();
	for(int i=0,c=0;i<sz && c<cnt1;i+=len1,c++) {
		for(int j=i;j<i+len1;j++) for(int k=j+1;k<i+len1;k++) e.push_back({arr[j],arr[k]});
	}
	for(int i=len1*cnt1,c=0;i<sz && c<cnt2;i+=len2,c++) {
		for(int j=i;j<i+len2;j++) for(int k=j+1;k<i+len2;k++) e.push_back({arr[j],arr[k]});
	}
	query(arr,e);
}

int richest(int nn,int t,int s) {
	n=nn;
	vector<int> arr;
	for(int i=0;i<n;i++) arr.push_back(i);
	if(n==1000) {
		solve1(arr.size(),arr);
		return arr[0];
	}
	solve1(2,arr),solve1(2,arr),solve1(2,arr),solve1(2,arr);
	solve2(3,20828,4,4,arr);
	solve1(6,arr);
	solve2(19,178,18,5,arr);
	solve1(arr.size(),arr);
	return arr[0];
}
/*
1099944
2 499951 2 49
2 249951 2 49
2 124951 2 49
2 62451 2 49
3 20828 4 4
6 3456 6 16
19 178 18 5
183 1 0 0
*/