#include <bits/stdc++.h>
using namespace std;
int g[8] = {500000, 250000, 125000, 62500, 20832, 3472, 183, 1};
int cnt[1000005];
vector<int> ask(vector<int> a, vector<int> b);
int richest(int N, int T, int S)
{
    int ttt = 8;
    if(N <= 1000){
        g[0] = 1;
        ttt = 1;
    }
    vector<int> res;
    res.reserve(N);
    for (int i = 0; i < N; i++)
        res.push_back(i);
    for (int i = 0; i < ttt; i++)
    {
        vector<int> a, b;
        int p = res.size() / g[i], G = res.size() % g[i]; // p: ppl in group, G: group+ num
        for (int k = 0; k < G; k++) // group+
        {
            int l = k * (p + 1), r = (k + 1) * (p + 1); // group [l,r) with p+1 ppl
            for (int I = l; I < r; I++)
            {
                for (int J = I + 1; J < r; J++)
                {
                    a.push_back(res[I]), b.push_back(res[J]); // do query
                }
            }
        }
        for (int k = G; k < g[i]; k++) // group
        {
            int l = G + k * p, r = G + (k + 1) * p; // group [l,r) with p ppl
            for (int I = l; I < r; I++)
            {
                for (int J = I + 1; J < r; J++)
                {
                    a.push_back(res[I]), b.push_back(res[J]);
                }
            }
        }
        vector<int> ans = ask(a, b);
        vector<int> res2; // new res
        int pos = 0;
        for (int k = 0; k < G; k++)
        {
            int l = k * (p + 1), r = (k + 1) * (p + 1);
            for (int I = l; I < r; I++)
            {
                for (int J = I + 1; J < r; J++)
                {
                    cnt[ans[pos++]]++; // count the larger
                }
            }
            for (int I = l; I < r; I++)
            {
                if (cnt[res[I]] == p)
                    res2.push_back(res[I]);
            }
            for (int I = l; I < r; I++)
                cnt[res[I]] = 0;
        }
        for (int k = G; k < g[i]; k++)
        {
            int l = G + k * p, r = G + (k + 1) * p;
            for (int I = l; I < r; I++)
            {
                for (int J = I + 1; J < r; J++)
                {
                    cnt[ans[pos++]]++;
                }
            }
            for (int I = l; I < r; I++)
            {
                if (cnt[res[I]] == p - 1)
                    res2.push_back(res[I]);
            }
            for (int I = l; I < r; I++)
                cnt[res[I]] = 0;
        }
        res = res2;
    }
    return res[0];
}