#include "richest.h"
#include <bits/stdc++.h>
#define _for(i, a, b) for (int i = a; i <= b; ++i)
#define for_(i, a, b) for (int i = a; i >= b; --i)
#define far(i, vec) for (auto i : vec)
#define bdmd int mid = (l + r) >> 1
typedef long double ldb;
typedef long long ll;
typedef double db;
typedef std::pair <int, int> pii;
typedef std::pair <ll, ll> pll;

std::vector <int> D ({ 500000, 250000, 125000, 62500, 20832, 3472, 183, 1 });

int richest(int N, int T, int S) {
    std::vector <int> A, C;
    _for (i, 0, N - 1) {
        A.emplace_back (i);
        C.emplace_back (0);
    }
    if (N == 1000) {
        std::vector <int> qi, qj;
        _for (i, 0, N - 1) _for (j, i + 1, N - 1)
            qi.emplace_back (i), qj.emplace_back (j);
        std::vector <int> ans = ask (qi, qj);
        int tot = 0;
        _for (i, 0, N - 1) _for (j, i + 1, N - 1)
            ++C[ans[tot]], ++tot;
        _for (i, 1, N) if (C[i] == N - 1)
            return i;
        return -1;
    }
    far (p, D) {
        std::vector <std::vector <int> > off (p);
        int m = A.size ();
        _for (i, 0, m - 1) {
            off[i % p].emplace_back (A[i]);
            C[A[i]] = 0;
        }
        std::vector <int> ().swap (A);
        std::vector <int> qi, qj;
        far (B, off) {
            int l = B.size ();
            _for (i, 0, l - 1) _for (j, i + 1, l - 1)
                qi.emplace_back (B[i]), qj.emplace_back (B[j]);
        }
        std::vector <int> ans = ask (qi, qj);
        int tot = 0;
        far (B, off) {
            int l = B.size ();
            _for (i, 0, l - 1) _for (j, i + 1, l - 1)
                ++C[ans[tot]], ++tot;
            _for (i, 0, l - 1) if (C[B[i]] == l - 1)
                A.emplace_back (B[i]);
        }
    }
    return A[0];
}