#include "richest.h"
#include <bits/stdc++.h>

int richest(int N, int T, int S) {
  std::vector<int> block;
  if (N == 1000) {
    block = {1000};
  } else {
    block = {2, 2, 2, 2, 3, 6, 19, 183};
  }
  std::vector<int> cand(N);
  std::iota(cand.begin(), cand.end(), 0);
  for (int bl : block) {
    // std::cerr << cand.size() << '\n';
    std::vector<int> ncand;
    std::vector<int> a, b;
    std::vector<int> nc(N);
    int r;
    for (int i = 0; i < std::ssize(cand); i = r + 1) {
      if (bl <= 6 && std::ssize(cand) - i < 2 * bl) {
        r = static_cast<int>(cand.size()) - 1;
      } else if (bl == 19 && i <= 72) {
        r = i + (bl - 1) - 1;
      } else {
        r = i + bl - 1;
      }
      for (int j = i; j <= r; ++j) {
        nc[cand[j]] = r - i;
        for (int k = j + 1; k <= r; ++k) {
          a.push_back(cand[j]);
          b.push_back(cand[k]);
        }
      }
      if (bl == 19 && i <= 72) {
        i -= 1;
      }
    }
    std::vector<int> t = ask(a, b);
    std::vector<int> freq(N);
    for (int i : t) {
      ++freq[i];
    }
    for (int i : cand) {
      if (freq[i] == nc[i]) {
        ncand.push_back(i);
      }
    }
    cand = ncand;
  }
  return cand[0];
}