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

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int NN = 1e6;

int arr[] = {500000, 250000, 125000, 62500, 20833, 3472, 183, 1};

int richest(int n, int t, int s) {
	int subt = 0;
	if (t == 1) subt = 7;
	
	vector <int> cur, ncur;
	if (!subt) for (int i = 0; i < NN; i++) cur.pb(i);
	else for (int i = 0; i < n; i++) cur.pb(i);
	
	for (int i = subt; i < 8; i++) {
		vector <int> v1, v2;
		ncur.clear();
		int x = cur.size(), k = arr[i];
		int y = x%k, z = x/k, uk = 0;
		int si[] = {y, k-y}, co[] = {z+1, z};
		for (int o = 0; o < 2; o++) {
			for (int i = 0; i < si[o]; i++) {
				for (int a = 0; a < co[o]; a++) for (int b = a+1; b < co[o]; b++) {
					if (uk+i*co[o]+b >= n) continue;
					v1.pb(cur[uk+i*co[o]+a]);
					v2.pb(cur[uk+i*co[o]+b]);
				}
			}
			uk += si[o]*co[o];
		}
		vector <int> v = ask(v1, v2);
		int br = 0; uk = 0;
		vector <int> deg(NN, 0);
		for (int o = 0; o < 2; o++) {
			for (int i = 0; i < si[o]; i++) {
				for (int a = 0; a < co[o]; a++) for (int b = a+1; b < co[o]; b++) {
					if (cur[uk+i*co[o]+b] < n) deg[v[br++]]++;
					else deg[cur[uk+i*co[o]+a]]++;
				}
				for (int a = 0; a < co[o]; a++) if (deg[cur[uk+i*co[o]+a]] == co[o]-1) ncur.pb(cur[uk+i*co[o]+a]);
			}
			uk += si[o]*co[o];
		}
		swap(ncur, cur);
	}
	return cur[0];
}