#include "richest.h"
#include <bits/stdc++.h>
// #define int int64_t
#define ALL(x) begin(x), end(x)
#define All(x, l, r) &x[l], &x[r] + 1
using namespace std;
using ll = long long;
template <typename T> using vec = vector<T>;

const int kLim = 1e6 + 5;
array<int, kLim> cnt;

vec<int> brute(const vec<vec<int>>& id) {
  int n = id.size();
  vec<int> a, b, l (n), r (n), res (n);
  int siz = 0;
  for(auto& k : id) siz += k.size() * (k.size() - 1) / 2;
  a.reserve(siz); b.reserve(siz);
  for(int i = 0; i < n; i++) {
    auto& v = id[i];
    l[i] = a.size();
    for(int j = 0; j < v.size(); j++)
      for(int k = j + 1; k < v.size(); k++) {
        a.push_back(v[j]);
        b.push_back(v[k]);
      }
    r[i] = a.size();
  }
  auto c = ask(a, b);
  for(int i = 0; i < n; i++) {
    auto& v = id[i];
    for(int j = l[i]; j < r[i]; j++) cnt[c[j]]++;
    for(int k : v)
      if(cnt[k] + 1 == v.size()) res[i] = k;
    for(int j = l[i]; j < r[i]; j++) cnt[c[j]]--;
  }
  return res;
}

int solve(vec<int> id, vec<int> way) {
  for(int i = 0; i < way.size(); i++) {
    int n = id.size();
    int c = way[i], q = n / c, r = n % c;
    vec<vec<int>> qry;
    vec<int> t (q + 1);
    for(int p = 0; p < n; ) {
      int siz = q + ((r--) > 0);
      if(t.size() > siz) t.pop_back();
      memcpy(&t[0], &id[p], siz * sizeof(int));
      p += siz; qry.push_back(t);
    }
    id = brute(qry);
  }
  return id[0];
}

int richest(int n, int T, int S) {
  vec<int> id (n);
  iota(ALL(id), 0);
  if(T == 1) return brute({id})[0];
  return solve(id, {500000, 250000, 125000, 62500, 20833, 3472, 183, 1});
}