#include<bits/stdc++.h>
using namespace std;
#include "richest.h"
bool vis[1000005];
int richest(int N, int T, int S) {
	if(N<=1000)
	{
		memset(vis,0,sizeof(vis));
		vector<int>a,b,c;
		for(int i=0;i<N;i++)
		{
			for(int j=i+1;j<N;j++)a.emplace_back(i),b.emplace_back(j);
		}
		c=ask(a,b);
		int tot=0;
		for(int i=0;i<N;i++)
		{
			for(int j=i+1;j<N;j++)
			{
				if(c[tot]==i)vis[j]=1;
				else vis[i]=1;
				tot++;
			}
		}
		for(int i=0;i<N;i++)if(!vis[i])return i;
	}
	memset(vis,0,sizeof(vis));
	for(int t=1;;t++)
	{
		vector<int>v,a,b,c;
		for(int i=0;i<N;i++)if(!vis[i])v.emplace_back(i);
		if(v.size()==1)return v[0];
		if(t<=3)for(int i=0;i<v.size();i+=2)
		{
			if(v.size()-i==1)continue;
			a.emplace_back(v[i]),b.emplace_back(v[i+1]);
		}
		else if(t<=5)for(int i=0;i<v.size();i+=3)
		{
			for(int j=0;j<=min((int)v.size()-i-1,2);j++)
			{
				for(int k=j+1;k<=min((int)v.size()-i-1,2);k++)a.emplace_back(v[i+j]),b.emplace_back(v[i+k]);
			}
		}
		else if(t<=8)for(int i=0;i<v.size();i+=8)
		{
			for(int j=0;j<=min((int)v.size()-i-1,7);j++)
			{
				for(int k=j+1;k<=min((int)v.size()-i-1,7);k++)a.emplace_back(v[i+j]),b.emplace_back(v[i+k]);
			}
		}
		else for(int i=0;i<v.size();i+=128)
		{
			for(int j=0;j<=min((int)v.size()-i-1,127);j++)
			{
				for(int k=j+1;k<=min((int)v.size()-i-1,127);k++)a.emplace_back(v[i+j]),b.emplace_back(v[i+k]);
			}
		}
		c=ask(a,b);
		for(int i=0;i<c.size();i++)
		{
			if(c[i]==a[i])vis[b[i]]=1;
			else vis[a[i]]=1;
		}
	}
}