#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
vector<int>v;
void work(int k){
    int n=v.size();
    vector<vector<bool>>o;
    vector<int>qa,qb;
    for(int s=0;s<n;s+=k){
        int len=min(k,n-s);
        rep(i,s,s+len-1){
            rep(j,i+1,s+len-1)qa.push_back(v[i]),qb.push_back(v[j]);
        }
    }
    vector<int>qans=ask(qa,qb);
    int cur=0;
    vector<int>nv;
    for(int s=0;s<n;s+=k){
        int len=min(k,n-s);
        vector<vector<bool>>o;
        o.resize(len);
        rep(i,0,len-1)o[i].resize(len);
        rep(i,s,s+len-1){
            rep(j,i+1,s+len-1){
                if(qans[cur]==v[i])o[i-s][j-s]=1,o[j-s][i-s]=0;
                else o[i-s][j-s]=0,o[j-s][i-s]=1;
                cur++;
            }
        }
        rep(i,s,s+len-1){
            bool fl=1;
            rep(j,s,s+len-1){
                if(i==j)continue;
                fl&=o[i-s][j-s];
            }
            if(fl){
                nv.push_back(v[i]);
                break;
            }
        }
    }
    v=nv;
}
int richest(int N, int T, int S) {
    v.clear();
    rep(i,0,N-1)v.push_back(i);
    if(N==1000){
        work(N);
        return v[0];
    }
    work(2),work(2),work(2),work(2),work(3),work(6),work(19),work(v.size());
    return v[0];
}