#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
mt19937 rd(time(0));
int n,t,s,vis[1000001];
int Sub1(){        
    vector<int> a,b,c;
    for(int i=0;i<n;i++){
        vis[i] = 0;
        for(int j=i+1;j<n;j++){
            a.pb(i),b.pb(j);
        }
    }
    c = ask(a,b);
    for(int i=0;i<c.size();i++){
        int u = a[i],v = b[i],w = c[i];
        if(u == w) vis[v] = 1;
        else vis[u] = 1;
    }
    int ans = 0;
    for(int i=0;i<n;i++) if(!vis[i]) ans = i;
    return ans;
}
int Sub2(){
    int cnt[8] = {1,183,3472,20833,62500,125000,250000,500000};
    vector<int> vec;
    for(int i=0;i<n;i++) vec.pb(i),vis[i] = 0; 
    for(int t=7;t>=0;t--){
        int len = n/cnt[t],y = n%cnt[t];
        vector<int> a,b,c,tmp;
        for(int l=0,r;l<n;l=r+1){
            if(y) r = l+len,y--;
            else r = l+len-1;
            for(int i=l;i<=r;i++){
                for(int j=i+1;j<=r;j++){
                    a.pb(vec[i]),b.pb(vec[j]);
                }
            }
        }
        c = ask(a,b);
        for(int i=0;i<c.size();i++){
            int u = a[i],v = b[i],w = c[i];
            if(u == w) vis[v] = 1;
            else vis[u] = 1;
        }
        for(int i=0;i<n;i++) if(!vis[vec[i]]) tmp.pb(vec[i]);
        vec.clear(),vec = tmp,n = vec.size();
    }
    return vec[0];
}
int richest(int N, int T, int S) {
    srand(time(0));
    n = N,t = T,s = S;
    if(N==1000 && T==1 && S==499500){
        return Sub1();
    }else{
        return Sub2();
    }
}