#include<bits/stdc++.h>
#include "richest.h"
using namespace std;
using ll=long long;
const int f[]={500000,250000,125000,62500,20833,3472,183,1};
const int N=1e6+5;
vector<int> v;
int cn[N];
void ak(int z){
    int n=v.size();
    if(n<=z)return;
    int len1=n%z;
    int len0=z-n%z;
    vector<int> s,t;
    for(int k=0;k<len1;++k){
        int l=k*(n/z+1);
        int r=(k+1)*(n/z+1)-1;
        for(int i=l;i<=r;++i){
            for(int j=i+1;j<=r;++j){
                s.push_back(v[i]);
                t.push_back(v[j]);
            }
        }
    }
    for(int k=0;k<len0;++k){
        int l=len1*(n/z+1)+k*(n/z);
        int r=l+n/z-1;
        for(int i=l;i<=r;++i){
            for(int j=i+1;j<=r;++j){
                s.push_back(v[i]);
                t.push_back(v[j]);
            }
        }
    }
    vector<int> as=ask(s,t);
    for(int i:as)cn[i]++;
    as.clear();
    for(int k=0;k<len1;++k){
        int l=k*(n/z+1);
        int r=(k+1)*(n/z+1)-1;
        for(int i=l;i<=r;++i){
            if(cn[v[i]]==n/z){
                as.push_back(v[i]);
            }
            cn[v[i]]=0;
        }
    }
    for(int k=0;k<len0;++k){
        int l=len1*(n/z+1)+k*(n/z);
        int r=l+n/z-1;
        for(int i=l;i<=r;++i){
            if(cn[v[i]]==n/z-1){
                as.push_back(v[i]);
            }
            cn[v[i]]=0;
        }
    }
    v=as;
}
int richest(int n,int t,int s){
    v.clear();
    for(int i=0;i<n;++i)v.push_back(i);
    if(t==1){
        ak(1);
        return v[0];
    }
    int cn=0;
    while(v.size()!=1){
        ak(f[cn]);++cn;
    }
    return v[0];
}