#include<bits/stdc++.h>
#include "richest.h"
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
//#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define rp(i,v) for(int i:v)
#define ford(i,n) for(int i=n-1;i>=0;i--)
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define vll vector<ll>
#define sz(s) (int)(s.size())
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 998244353
/************************************************/
using namespace std;
//int cnt[1001];
int a[8]={1,183,3472,20832,62500,125000,250000,500000};
//vi ask(vi x,vi y){
//	vi res;
//	rep(i,sz(x)){
//		cout<<x[i]<<" "<<y[i]<<"\n";
//		int ab;cin>>ab;
//		res.pb(ab);
//	}
//	re res;
//}
int richest(int n,int s,int t){
	int cnt[1000001];
	vi now;
	forn(i,0,n)
	now.pb(i);
	forn(i,0,n+1)
	cnt[i]=0;
	if(n<=1000){
		vi aa,ab;
		aa.clear();
		ab.clear();
		forn(i,0,n)
		forn(j,i+1,n){
			aa.pb(i);
			ab.pb(j);
		}
		vi res=ask(aa,ab);
		rep(i,sz(res)){
			cnt[res[i]]++;
		}
		forn(i,0,n){
			if(cnt[i]==n-1)
			return i;
		}
	}
	ford(i,8){
		int c1=a[i]-n%a[i],c2=n%a[i];
		int l1=n/a[i],l2=n/a[i]+1;
		vi nxt;
		int j=0;
			vi aa,bb;
		while(c1--){
			forn(i1,j,j+l1)
			forn(j1,i1+1,j+l1){
				aa.pb(now[i1]);
				bb.pb(now[j1]);
			}
			forn(i1,j,j+l1)
			cnt[now[i1]]=0;
			j+=l1;
		} 
		while(c2--){
			forn(i1,j,j+l2)
			forn(j1,i1+1,j+l2){
				aa.pb(now[i1]);
				bb.pb(now[j1]);
			}
			forn(i1,j,j+l2)
			cnt[now[i1]]=0;
			
			j+=l2;
		}
		vi res=ask(aa,bb);
		rep(ii,sz(res))
		cnt[res[ii]]++;
		c1=a[i]-n%a[i],c2=n%a[i];
		j=0;
		while(c1--){
			
			forn(i1,j,j+l1)
			if(cnt[now[i1]]==l1-1)
			nxt.pb(now[i1]);
			j+=l1;
		}
		while(c2--){
			forn(i1,j,j+l2)
			if(cnt[now[i1]]==l2-1)
			nxt.pb(now[i1]);
			j+=l2;
		}
		now=nxt;
		n=a[i];
	}
	re now[0];
} 
//int main(){
//	cout<<richest(4,0,0);
//	return 0;
//}
/*
检查循环是rep(i,n)还是rep(i,m)!!
long long所要的时间比int长!!
没有long long必要不写long long!!
写公式前先想一想!!
二分前看一看边界对不对，有没有特殊值!!
提交前要测特殊数据（边界上的）!!
比较模数时如有负数，需要+mod!!
*/