#include"richest.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+99;
int grp[10]={0,500000,250000,125000,62500,20833,3472,183,1};
int cnt[N];
int richest(int n,int T,int S){
	vector<int> ans;
	for(int i=0;i<n;i++)
		ans.push_back(i);
	if(T==1){
		vector<int> a,b,c;
    	for(int j=0;j<ans.size();j++)
			for(int k=j%1;k<j;k+=1)
				 a.push_back(ans[j]),b.push_back(ans[k]);
		c=ask(a,b);
		memset(cnt,0,sizeof(cnt));
		for(int j=0;j<c.size();j++)
			if(c[j]==a[j]) cnt[b[j]]++;
			else cnt[a[j]]++;
		vector<int> nid;
		for(int j=0;j<ans.size();j++)
			if(!cnt[ans[j]])
				nid.push_back(ans[j]);
		swap(nid,ans);
		return ans[0];
	}
    for(int i=1;i<=8;i++){
    	vector<int> a,b,c;
    	for(int j=0;j<ans.size();j++)
			for(int k=j%grp[i];k<j;k+=grp[i])
				 a.push_back(ans[j]),b.push_back(ans[k]);
		c=ask(a,b);
		memset(cnt,0,sizeof(cnt));
		for(int j=0;j<c.size();j++)
			if(c[j]==a[j]) cnt[b[j]]++;
			else cnt[a[j]]++;
		vector<int> nid;
		for(int j=0;j<ans.size();j++)
			if(!cnt[ans[j]])
				nid.push_back(ans[j]);
		swap(nid,ans);
	}
    return ans[0];
}