#include<bits/stdc++.h>
#include "richest.h"

using namespace std;
const int NR=1e6+10;
bool vis[NR];
int n;
const int val[]={0,2,2,2,2,3,6,19,183};
#define pb emplace_back

int from[NR];
int dfs(int col,vector<int> idx){
	if(idx.size()==1)return idx[0]-1;
	cerr<<col<<" "<<idx.size()<<endl;
	int len=idx.size();
	for(int i=0;i<len;i++)from[i]=i/val[col];
	vector<int>a,b;
	for(int i=0;i<len;i++)
		for(int j=i+1;j<len;j++)
			if(from[i]==from[j])a.pb(idx[i]-1),b.pb(idx[j]-1);
			else break;
	vector<int>c=ask(a,b);
	for(int i=0;i<c.size();i++)
		if(c[i]==a[i])vis[b[i]+1]=1;
		else vis[b[i]+1]=1;
	vector<int>nidx;
	for(int i=0;i<len;i++)
		if(!vis[idx[i]])nidx.pb(idx[i]);
	return dfs(col+1,nidx);
}

int richest(int N, int T, int S){
	n=N;
	memset(vis,0,sizeof(vis));
	if(N=1000){
		vector<int>a,b;
		for(int i=1;i<n;i++)
			for(int j=i+1;j<=n;j++)
				a.pb(i-1),b.pb(j-1);
		vector<int>c=ask(a,b);
		for(int i=0;i<c.size();i++)
			if(c[i]==a[i])vis[b[i]+1]=1;
			else vis[a[i]+1]=1;
		for(int i=1;i<=n;i++)
			if(!vis[i])return i-1;
	}
	vector<int>tmp;
	for(int i=1;i<=n;i++)tmp.pb(i);
    return dfs(1,tmp);
}