#include<bits/stdc++.h>
using namespace std;
std::vector<int> ask(std::vector<int> a, std::vector<int> b);
int richest(int N, int T, int S)
{
	vector<int>now,v;
	now.clear();v.clear();
	v.resize(N+1,0);
	for(int i=1;i<=N;i++)
	now.push_back(i);
	if(T==1)
	{
		vector<int>a,b;
		a.clear(),b.clear();
		for(int i=0;i<now.size();i++)
		{
			for(int j=i+1;j<now.size();j++)
			{
				a.push_back(now[i]-1);
				b.push_back(now[j]-1);
			}
		}
		vector<int> c=ask(a,b);
		for(int i=0;i<c.size();i++)
		{
			v[(a[i]^b[i]^c[i])+1]=1;
		}
		for(int i=1;i<=N;i++)
		if(!v[i])
		{
			return i-1;
		}
	}
	int siz[8]={0,500000,250000,125000,62496,20832,3472,183};
	/*
	1099944 1000000
	599944 500000
	349944 250000
	224944 125000
	162432 62496
	99936 20832
	47856 3472
	16653 183
	0 1
	*/
	for(int p=1;p<=7;p++)
	{
		int k=now.size()/siz[p];
		int num=now.size()%siz[p];
		vector<vector<int> >tp;
		tp.clear();
		for(int i=1;i<=siz[p];i++)
		{
			tp.push_back({});
		}
		int lst=0;
		int tnum=0;
		for(int t=0;t/k<siz[p];t+=k)
		{
			tnum++;
			lst=t+k-1;
			for(int j=0;j<k;j++)
			tp[t/k].push_back(now[t+j]);
		}
		// cerr<<now.size()<<' '<<lst+1<<' '<<siz[p]*k<<' '<<siz[p]<<' '<<tnum<<' '<<k<<' '<<tp[siz[p]-1].size()<<'\n';
		for(int j=lst+1;j<now.size();j++)
		{
			// cerr<<j-lst-1<<' '<<siz[p]<<endl;
			tp[j-lst-1].push_back(now[j]);
		}
		vector<int>a;
		vector<int>b;
		a.clear();
		b.clear();
		int tt=0;
		for(int t=0;t<siz[p];t++)
		{
			for(int i=0;i<tp[t].size();i++)
			for(int j=i+1;j<tp[t].size();j++)
			{
				a.push_back(tp[t][i]-1);
				b.push_back(tp[t][j]-1);
			}
			if(tp[t].size()>k)
			tt++;
		}
		vector<int>c=ask(a,b);
		for(int i=0;i<c.size();i++)
		{
			v[(a[i]^b[i]^c[i])+1]=1;
		}
		// cerr<<tt<<' '<<num<<'\n';
		vector<int>newn;
		newn.clear();
		for(auto u:now)
		{
			if(!v[u])
			newn.push_back(u);
		}
		now.clear();
		swap(now,newn);
	}
	vector<int>a,b;
	a.clear(),b.clear();
	for(int i=0;i<now.size();i++)
	{
		for(int j=i+1;j<now.size();j++)
		{
			a.push_back(now[i]-1);
			b.push_back(now[j]-1);
		}
	}
	vector<int> c=ask(a,b);
	for(int i=0;i<c.size();i++)
	{
		v[(a[i]^b[i]^c[i])+1]=1;
	}
	// cerr<<c.size()<<'\n';
	for(int i=1;i<=N;i++)
	if(!v[i])
	{
		return i-1;
	}
}
/*


1099944 1000000
599944 500000
349944 250000
224944 125000
162432 62496
99936 20832
47856 3472
16653 183
0 1



*/