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

using namespace std;

namespace {
int cnt[1000005];
void solve(vector<int> &cur, int len, int c1, int c2) {
  memset(cnt, 0, sizeof(cnt));
  int N = cur.size();
  assert(len * c1 + (len + 1) * c2 == N);
  vector<int> a, b;
  for (int i = 0; i < c1; i++) {
    for (int j = i * len; j < (i + 1) * len; j++) {
      for (int k = j + 1; k < (i + 1) * len; k++) {
        a.emplace_back(cur[j]), b.emplace_back(cur[k]);
      }
    }
  }
  for (int i = 0; i < c2; i++) {
    for (int j = i * (len + 1); j < (i + 1) * (len + 1); j++) {
      for (int k = j + 1; k < (i + 1) * (len + 1); k++) {
        a.emplace_back(cur[c1 * len + j]), b.emplace_back(cur[c1 * len + k]);
      }
    }
  }
  vector<int> c = ask(a, b), d;
  int _id = 0;

  for (int i = 0; i < c1; i++) {
    for (int j = i * len; j < (i + 1) * len; j++)
      for (int k = j + 1; k < (i + 1) * len; k++)
        cnt[c[_id++]]++;
    int p = -1;
    for (int j = i * len; j < (i + 1) * len; j++)
      if (cnt[cur[j]] == len - 1) {
        p = j;
        break;
      }
    assert(~p), d.emplace_back(cur[p]);
  }
  for (int i = 0; i < c2; i++) {
    for (int j = i * (len + 1); j < (i + 1) * (len + 1); j++)
      for (int k = j + 1; k < (i + 1) * (len + 1); k++)
        cnt[c[_id++]]++;
    int p = -1;
    for (int j = i * (len + 1); j < (i + 1) * (len + 1); j++)
      if (cnt[cur[c1 * len + j]] == len) {
        p = j;
        break;
      }
    assert(~p), d.emplace_back(cur[c1 * len + p]);
  }
  assert(d.size() == c1 + c2), cur.swap(d);
}
} // namespace

int richest(int N, int T, int S) {
  vector<int> cur(N);
  iota(cur.begin(), cur.end(), 0);
  if (N == 1000) {
    solve(cur, 1000, 1, 0);
    assert(cur.size() == 1);
    return cur[0];
  }
  assert(N == 1'000'000);
  for (int _ = 1; _ <= 4; _++) {
    if (N == 1)
      return cur[0];
    vector<int> a(N / 2), b(N / 2);
    for (int i = 0; i < N / 2; i++)
      a[i] = cur[i * 2], b[i] = cur[i * 2 + 1];
    vector<int> c = ask(a, b);
    c.swap(cur), N = cur.size();
  }
  // cerr << cur.size() << '\n';
  solve(cur, 3, 20832, 1);
  solve(cur, 6, 3471, 1);
  solve(cur, 18, 5, 178);
  solve(cur, 183, 1, 0);
  return cur[0];
}