#include <bits/stdc++.h>
#include "richest.h"
using namespace std;
const int MAXN = 1e6 + 5;
// std::vector<int> ask(std::vector<int> a, std::vector<int> b);
int sol[8] = {500000, 250000, 125000, 62500, 20833, 3472, 183, 1};
int cnt[MAXN];
vector <int> a, b, res;
vector <int> v;
void Ask(int l, int r){
    for (int i = l; i <= r; i++){
        for (int j = i + 1; j <= r; j++){
            a.push_back(v[i]);
            b.push_back(v[j]);
        }
    }
}
void Solve(){
    res.clear();
    res = ask(a, b);
    a.clear(), b.clear();
    for (int i = 0; i < MAXN; i++)
        cnt[i] = 0;
    for (auto x: res)
        cnt[x]++;
}
int Ans(int l, int r){
    int len = r - l + 1;
    for (int i = l; i <= r; i++)
        if (cnt[v[i]] == len - 1)
            return v[i];
}
vector <pair <int, int> > now;
int richest(int N, int T, int S){
    v.clear();
    for (int i = 0; i < N; i++)
        v.push_back(i);
    if (N == 1000){
        Ask(0, 999);
        Solve();
        return Ans(0, 999);
    }else{
        int n = N;
        for (int i = 0; i < 8; i++){
            int num = sol[i];
            int cnt1 = num - n % num, len1 = n / num, cnt2 = n % num, len2 = n / num + 1;
            now.clear();
            for (int i = 1; i <= cnt1; i++)
                now.push_back({(i - 1) * len1, i * len1 - 1});
            for (int i = 1; i <= cnt2; i++)
                now.push_back({cnt1 * len1 + (i - 1) * len2, cnt1 * len1 + i * len2 - 1});
            for (auto x: now)
                Ask(x.first, x.second);
            Solve();
            v.clear();
            for (auto x: now)
                v.push_back(Ans(x.first, x.second));
            n = num;
        }
        return v[0];
    }
}