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

int Force(std::vector<int> id) {
  int N = (int) id.size();
  std::vector g(N, std::vector<bool>(N));
  std::vector<int> A, B;
  for (int i = 0; i < N; i++)
    for (int j = i + 1; j < N; j++) {
      A.emplace_back(id[i]);
      B.emplace_back(id[j]);
    }
  auto res = ask(A, B);
  for (int i = 0, tot = 0; i < N; i++)
    for (int j = i + 1; j < N; j++) {
      int c = res[tot++] == id[i];
      g[i][j] = c, g[j][i] = !c;
    }
  for (int i = 0; i < N; i++) {
    int cnt = 0;
    for (int j = 0; j < N; j++)
      cnt += g[i][j];
    if (cnt == N - 1)
      return id[i];
  }
  return -1;
}

int richest(int N, int T, int S) {
  std::vector<int> cur;
  for (int i = 0; i < N; i++)
    cur.emplace_back(i);

  if (T == 1) return Force(cur);

  for (int step = 0; step < 8; step++) {
    int m = (int) cur.size(), ext = -1;
    std::vector<int> A, B;

    for (int i = 0; i + 1 < m; i += 2) {
      A.emplace_back(cur[i]);
      B.emplace_back(cur[i ^ 1]);
    }

    if (m & 1) ext = cur.back();
    cur = ask(A, B);
    if (~ext) cur.emplace_back(ext);
  }

  {
    const int SI = 40;
    std::vector<int> A, B;
    int m = (int) cur.size();

    for (int l = 0; l < m; l++) {
      int r = std::min(l + SI, m) - 1;
      for (int i = l; i <= r; i++)
        for (int j = i + 1; j <= r; j++) {
          A.emplace_back(cur[i]);
          B.emplace_back(cur[j]);
        }
      l = r;
    }

    std::vector<int> tmp;
    auto res = ask(A, B);

    int tot = 0;

    for (int l = 0; l < m; l++) {
      int r = std::min(l + SI, m) - 1, len = r - l + 1;
      std::vector g(m, std::vector<bool>(m));
      for (int i = l; i <= r; i++)
        for (int j = i + 1; j <= r; j++) {
          int c = res[tot++] == cur[i];
          g[i][j] = c, g[j][i] = !c;
        }
      for (int i = l; i <= r; i++) {
        int cnt = 0;
        for (int j = l; j <= r; j++)
          cnt += g[i][j];
        if (cnt == len - 1)
          tmp.emplace_back(cur[i]);
      }
      l = r;
    }
    cur = tmp;
  }

  return Force(cur);
}

/*
 * 1000000 20 2000000 1
 * 998,046 + 1954
 */