#include "richest.h"
#include <bits/stdc++.h>
// #include "grader.cpp"

using namespace std;

const int maxn=1e6+5;

int bg[maxn];
int f[8]={500000,250000,125000,62500,20832,3472,183,1};

int richest(int n,int T,int S) {
    if(T==1) {
        vector<int> a, b, c;
        for(int i=0;i<n;i++) {
            bg[i]=a.size()-1;
            for(int j=i+1;j<n;j++) {
                a.push_back(i);
                b.push_back(j);
            }
        }
        c=ask(a,b);
        int x=0;
        for(int i=1;i<n;i++) {
            if(c[bg[x]+i-x]==x) ;
            else x=i;
        }
        return x;
    }
    vector<int> vec, vec2;
    for(int i=0;i<n;i++) vec.push_back(i);
    for(int p=0;p<8;p++) {
        n=vec.size();
        int t=f[p], r=n%t, v=n/t;
        vector<int> a,b,c;
        int pos=0;
        for(int i=1;i<=t;i++) {
            int v2=v+(i<=r);
            for(int j=pos;j<pos+v2;j++) {
                bg[j]=a.size()-1;
                for(int j2=j+1;j2<pos+v2;j2++) {
                    a.push_back(vec[j]);
                    b.push_back(vec[j2]);
                }
            }
            pos+= v2;
        }
        c=ask(a,b);
        pos=0;
        for(int i=1;i<=t;i++) {
            int v2=v+(i<=r);
            int x=pos;
            for(int j=pos+1;j<pos+v2;j++) {
                if(c[bg[x]+j-x]==vec[x]) ;
                else x=j;
            }
            vec2.push_back(vec[x]);
            pos+= v2;
        }
        vec=vec2, vec2.clear();
    }
    return vec[0];
}