#include "richest.h"

#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;using pii=pair<int,int>;
const int N=1e6+5,M=N*100+5,K=1e7+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const ll INF=5e18+7;mt19937 rnd(time(0));
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;

int vis[N];
int pre[8]={1,183,3472,20832,62500,125000,250000,500000};
int A[N],B[N],Ah,Bh;
int richest(int n, int T, int S) {
	if(T==1){
		vector<int> a(n*(n-1)/2),b(n*(n-1)/2);int m=0;
		for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) a[m]=i,b[m]=j,m++;
		auto c=ask(a,b);
		fill(vis,vis+n,0);
		for(int i=0;i<m;i++) vis[a[i]^b[i]^c[i]]=1;
		return find(vis,vis+n,0)-vis;
	}
	Ah=0;
	for(int i=0;i<n;i++) A[++Ah]=i;
	for(int i=7;~i;i--){
		Bh=Ah;copy(A+1,A+Ah+1,B+1);Ah=0;
		int x=n/pre[i],y=n%pre[i];
		int m=x*(x+1)/2*y+x*(x-1)/2*(pre[i]-y);
		vector<int> a(m),b(m);
		m=0;
		for(int j=1;j<=pre[i];j++){
			int z=x;
			if(j<=y) z++;
			for(int x=Bh-z+1;x<=Bh;x++) for(int y=x+1;y<=Bh;y++) a[m]=B[x],b[m]=B[y],m++;
			Bh-=z;
		}
		auto c=ask(a,b);
		for(int j=1;j<=n;j++) vis[B[j]]=0;
		for(int j=0;j<m;j++) vis[a[j]^b[j]^c[j]]=1;
		for(int j=1;j<=n;j++) if(!vis[B[j]]) A[++Ah]=B[j];
		n=Ah;
	}
	assert(n==1);
	return A[1];
}