#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 = 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[i] == len - 1)
            return v[i];
    return -1;
}
vector <pair <int, int> > now;
int richest(int N, int T, int S){
    if (N == 1000){
        Ask(0, 999);
        Solve();
        return Ans(0, 999);;
    }else{
        int n = N;
        for (int i = 0; i < 8; i++){
            int x = sol[0];
            int cnt1 = x - n % x, len1 = n / x, cnt2 = n % x, len2 = n / x + 1;
            now.clear();
            for (int i = 1; i <= cnt1; i++)
                now.push_back({(i - 1) * len1 + 1, i * len1});
            for (int i = 1; i <= cnt2; i++)
                now.push_back({cnt1 * len1 + (i - 1) * len2 + 1, cnt1 * len1 + i * len2});
            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 = x;
        }
    }
}