#include "richest.h"
#include<bits/stdc++.h>
#define F(i,a,b) for(int i(a),i##E(b);i<=i##E;i++)
#define UF(i,a,b) for(int i(a),i##E(b);i>=i##E;i--)
#define gc getchar
#define sz(x) int((x).size())
#define vec vector
#define File(x) (freopen(x".in","r",stdin),freopen(x".out","w",stdout))
using namespace std;using ll=long long;using ull=unsigned long long;
template<class T>
void operator+=(vec<T> &a,const T&b) {a.push_back(b);}
std::vector <int> ask(std::vector <int> a, std::vector <int> b);
//std::vector <int> ask(std::vector <int> a, std::vector <int> b) {
//	return {}; 
//}
const int A[]{0,2,2,2,2,3,6,19,10000000};
int nid[int(1e6+5)];
void addval(vec<int> &a,vec<int> &b,int st,int val) {
	F(i,0,val-1) F(j,i+1,val-1) a+=i+st,b+=j+st;
}
int rich(int dep,int n,vec<int> id) {
	assert(dep<=8);
	int x=A[dep];
	vec<int> a,b;
	vec<bool> NOT(n);
	F(i,0,n-1) nid[id[i]]=i;
	if(n<x) {
		addval(a,b,0,n);
	} else if(n%x==0) {
		F(i,0,n/x-1) addval(a,b,i*x,x);
	} else {
		int now=0;
		F(i,1,n/x-(x-1-n%x)) addval(a,b,now,x),now+=x;
		F(i,1,(x-n%x)) addval(a,b,now,x-1),now+=x-1;
		assert(now==n);
	}
	for(int &x:a) x=id[x];
	for(int &x:b) x=id[x];
	vec<int> c=ask(a,b);
	F(i,0,n-1) NOT[nid[a[i]^b[i]^c[i]]]=1;
	vec<int> newid;
	F(i,0,n-1) if(!NOT[i]) newid+=id[i];
	if(sz(newid)==1) return newid[0];
	return rich(dep+1,(n+x-1)/x,newid);
}
int richest(int n,int T,int S) {
	if(n==1000) {
		vec<int> a,b;
		vec<bool> NOT(n);
		F(i,0,n-1) F(j,i+1,n-1) a+=i,b+=j;
		vec<int> c=ask(a,b);
		F(i,0,n-1) NOT[a[i]^b[i]^c[i]]=1;
		F(i,0,n-1) if(!NOT[i]) return i;
		return 114514;
	}
	vec<int> id(n);
	F(i,0,n-1) id[i]=i+1;
	return rich(1,n,id);
	
}
//main() {}