#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include "richest.h"
using namespace std;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int cnt[1000005];
vector<int>init(vector<int>a,vector<int>b){
	memset(cnt,0,sizeof(cnt));
	vector<int>res,now;
	for(auto x:a){
		cnt[x]++;
	}
	for(auto x:b){
		cnt[x]++;
	}
	res = ask(a,b);
	for(auto x:res){
		cnt[x]--;
		if(!cnt[x]){
			now.push_back(x);
		}
	}
	return now;
}
vector<int>a,b,c;
void merge(int x,int y,int z){//前x个分成y大小，其余的z大小 
	int sz = a.size();
	b.clear();c.clear();
	for(int i=0;i<x;i++){
		int l = i,r = i+y-1;
		for(int j=l;j<=r;j++){
			for(int k=j+1;k<=r;k++){
				if(j>=sz||k>=sz){
					continue;
				}
				b.push_back(a[j]);
				c.push_back(a[k]);
			}
		}
	}
	for(int i=x*y;i<sz;i+=z){
		int l=i,r=i+z-1;
		for(int j=l;j<=r;j++){
			for(int k=j+1;k<=r;k++){
				if(j>=sz||k>=sz){
					continue;
				}
				b.push_back(a[j]);
				c.push_back(a[k]);
			}
		}
	}
	a = init(b,c);
}
int richest(int N,int T,int S){
	if(N==1000&&S==499500){
		vector<int>res;
		a.clear();b.clear();
		bool vis[1005][1005];
		memset(vis,0,sizeof(vis)); 
		for(int i=1;i<=N;i++){
			for(int j=i+1;j<=N;j++){
				a.push_back(i);
				b.push_back(j);
			}
		}
		int tt = 0;
		res = ask(a,b);
		for(int i=1;i<=N;i++){
			for(int j=i+1;j<=N;j++){
				vis[i][j] = res[tt]==i;
				vis[j][i] = vis[i][j]^1;
				tt++;
			}
		}
		int mx = 1;
		for(int i=2;i<=N;i++){
			if(!vis[mx][i]){
				mx = i;
			}
		}
		return mx;
	}
	a.clear();b.clear();c.clear();
	for(int i=1;i<=N;i++){
		a.push_back(i);
	}
	for(int i=1;i<=4;i++){
		int sz = a.size();
		b.clear();c.clear();
		for(int i=0;i<sz;i+=2){
			b.push_back(a[i]);
		}
		for(int i=1;i<sz;i+=2){
			c.push_back(a[i]);
		}
		a = init(b,c);
	}
	merge(2,2,3);
	merge(4,5,6);
	merge(4,18,19);
	int sz = a.size();
	if(sz!=1){
		merge(1,sz,sz+1);
	}
	return a[0];
}