#include "richest.h"

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll id[1005][1005],id2[1000005],ls[10]={500000,250000,125000,62500,20833,3472,183,1};

int richest(int N, int T, int S) {
	if (T==1){
		vector<int> vct1,vct2;
		ll tot=-1;
		for (ll i=0;i<N;i++){
			for (ll j=i+1;j<N;j++){
				vct1.push_back(i);
				vct2.push_back(j);
				id[i][j]=++tot;
			}
		}
		vector<int> p=ask(vct1,vct2);
		for (ll i=0;i<N;i++){
			ll c=0;
			for (ll j=0;j<N;j++){
				if (i!=j){
					if (j<i){
						c+=p[id[j][i]]==i;
					}else{
						c+=p[id[i][j]]==i;
					}
				}
			}
			if (c==N-1){
				return i;
			}
		}
	}
	for (ll i=0;i<=N;i++)id2[i]=0;
	vector<int> all;
	for (ll i=0;i<N;i++)all.push_back(i);
	for (ll i=0;i<8;i++){
		ll tot=all.size();
		vector<vector<int>> vct;
		vct.resize(ls[i]+1);
		ll ps=0;
		for (ll j=0;j<tot;j++){
			vct[ps].push_back(all[j]);ps++;ps%=ls[i];
		}
		vector<int> p1,p2;
		for (ll j=0;j<ls[i];j++){
			for (ll k=0;k<vct[j].size();k++){
				for (ll l=k+1;l<vct[j].size();l++){
					p1.push_back(vct[j][k]);p2.push_back(vct[j][l]);
				}
			}
		}
		
		vector<int> p3=ask(p1,p2),p4;
		ll rk=-1;
		for (ll j=0;j<ls[i];j++){
			
			ll tot2=-1;
			for (ll k=0;k<vct[j].size();k++)id2[vct[j][k]]=++tot2;
			vector<int> cnt;
			cnt.resize(tot2+2);
			for (ll k=0;k<vct[j].size();k++){
				for (ll l=k+1;l<vct[j].size();l++){
					++rk;
					cnt[id2[p3[rk]]]++;
				}
			}
			for (ll k=0;k<vct[j].size();k++)if (cnt[id2[vct[j][k]]]==vct[j].size()-1)p4.push_back(vct[j][k]);
		}
		all=p4;
	}
    return all[0];
}