#include "richest.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
const int num[9]={500000,250000,125000,62496,20832,3472,183,1};
vector<int> vec;
bool vis[MAXN];
int _[1005][1005];
int richest(int n,int T,int S) {
    if(T==1) {
        vector<int> A,B;
        for(int i=0;i<n;++i) {
            for(int j=i+1;j<n;++j) {
                A.emplace_back(i),B.emplace_back(j);
            }
        }
        auto C=ask(A,B);
        for(int i=0,k=0;i<n;++i) {
            for(int j=i+1;j<n;++j) {
                _[i][j]=C[k++];
            }
        }
        int mx=0;
        for(int i=1;i<n;++i) {
            if(_[mx][i]==i) mx=i;
        }
        return mx;
    }
    else {
        for(int i=0;i<n;++i) vec.emplace_back(i);
        for(int i=0;i<8;++i) {
            vector<int> A,B;
            int k=num[i],len=vec.size();
            for(int j=0;j<len;++j) vis[j]=1;
            for(int j=0;j<k;++j) {
                for(int t=j;t<len;t+=k) {
                    for(int l=t+k;l<len;l+=k) {
                        A.emplace_back(vec[t]);
                        B.emplace_back(vec[l]);
                    }
                }
            }
            auto C=ask(A,B);
            for(int j=0,cnt=0;j<k;++j) {
                for(int t=j;t<len;t+=k) {
                    for(int l=t+k;l<len;l+=k) {
                        if(C[cnt++]==vec[t]) vis[l]=0;
                        else vis[t]=0;
                    }
                }
            }
            vector<int> tmp;
            for(int j=0;j<len;++j) {
                if(vis[j]) tmp.emplace_back(vec[j]);
            }
            vec=tmp;
            assert(vec.size()==k);
        }
        return vec[0];
    }
}