#include "richest.h"
#include<bits/stdc++.h>
//#define int long long
//#define ull unsigned int
//#define lll __int128
//#define double long double
using namespace std;
const long long INF=1e9+5;
//const long long mod=998244353,orm=3;
const long long mod=1000000007;
const int MAXN=2000005;
const double eps=1e-6;
vector<pair<int,int> > v2[MAXN],v[MAXN];
vector<int> A,B,ans,v3[MAXN];
int n,B1=2,B2=1000,B3=20,rt=0,tot=0;
int d[MAXN],be[MAXN],vis[MAXN];
int son[MAXN][22];
void calc(int dep,int &k,int l,int r) {
	k=++tot,d[k]=dep;
	int len=r-l+1;
	if(len==1) {
		be[k]=l;
		return ;
	}
	if(len<=B1) {
		for(int i=l;i<=r;i++) {
			for(int j=i+1;j<=r;j++) v[k].push_back({i,j});
		}
		return ;
	}
	if(len>=B2) {
		int sz=len/B3;
		for(int i=1;i<B3;i++) {
			calc(dep+1,son[k][++son[k][0]],l,l+sz-1);l+=sz;
		}
		if(l<=r) calc(dep+1,son[k][++son[k][0]],l,r);
		for(int i=1;i<=son[k][0];i++) {
			for(int j=i+1;j<=son[k][0];j++) {
				v2[k].push_back({son[k][i],son[k][j]});
			}
		}
		return ;
	}
	int sz=len/B1;
	for(int i=1;i<B1;i++) {
		calc(dep+1,son[k][++son[k][0]],l,l+sz-1);l+=sz;
	}
	if(l<=r) calc(dep+1,son[k][++son[k][0]],l,r);
	for(int i=1;i<=son[k][0];i++) {
		for(int j=i+1;j<=son[k][0];j++) {
			v2[k].push_back({son[k][i],son[k][j]});
		}
	}
}
void clear() {
	A.clear(),B.clear(),ans.clear();
}
void Clear() {
	for(int i=0;i<=max({tot,n,100});i++) {
		son[i][0]=d[i]=be[i]=vis[i]=0;
		v[i].clear(),v2[i].clear(),v3[i].clear();
	}
	clear();
	tot=0;rt=0;
}
int O=0,O2=0;
int richest(int N, int T, int S) {
	n=N;
	if(n<=1000) B1=1000;
	calc(0,rt,1,n);
	for(int i=1;i<=tot;i++) {
		for(auto p:v[i]) {
			A.push_back(p.first-1),B.push_back(p.second-1);
		}
	}
	ans=ask(A,B);int nw=0;
	for(int i=1;i<=tot;i++) {
		int id=0;
		for(auto p:v[i]) {
			if(ans[nw++]==p.first-1) vis[p.second]=1;
			else vis[p.first]=1;
		}
		for(auto p:v[i]) {
			if(!vis[p.first]) id=p.first;
			if(!vis[p.second]) id=p.second;
		}
		if(v[i].size()) be[i]=id;
	}
	clear();nw=0;
	int mx=0;
	for(int i=1;i<=tot;i++) v3[d[i]].push_back(i),mx=max(mx,d[i]);
	for(int i=mx;i>=0;i--) {
		for(int j:v3[i]) {
			for(auto p:v2[j]) {
				if(!be[p.first]||!be[p.second]) {
					cout<<be[p.first]<<" "<<be[p.second]<<"\n";
					cout<<v[p.first].size()<<" "<<v[p.second].size()<<"\n";
					assert(0);
				}
				A.push_back(be[p.first]-1),B.push_back(be[p.second]-1);
			}
		}
		if(A.size()) ans=ask(A,B);nw=0;
		for(int j:v3[i]) {
			for(auto p:v2[j]) {
				if(ans[nw++]==be[p.first]-1) vis[be[p.second]]=1;
				else vis[be[p.first]]=1;
			}
			int id=0;
			for(auto p:v2[j]) {
				if(!vis[be[p.first]]) id=be[p.first];
				if(!vis[be[p.second]]) id=be[p.second];
			}
			if(v2[j].size()) be[j]=id;
		}
		clear();nw=0;
	}
	int res=be[rt];Clear();
	return res-1;
}