#include <algorithm>
#include <cstdio>
#include <cmath>

#include "richest.h"

int refer[1000007], mx[1007][1007];

inline int onequery(std::vector<int> v){
	int ans = 0;
	std::vector<int> a, b, c;
	for (int i = 0; i < v.size(); i++){
		refer[v[i]] = i;
	}
	for (int i = 0; i + 1 < v.size(); i++){
		for (int j = i + 1; j < v.size(); j++){
			a.push_back(v[i]);
			b.push_back(v[j]);
		}
	}
	c = ask(a, b);
	for (int i = v.size() - 2; i >= 0; i--){
		for (int j = v.size() - 1; j > i; j--){
			mx[i][j] = mx[j][i] = refer[c.back()];
			c.pop_back();
		}
	}
	for (int i = 1; i < v.size(); i++){
		ans = mx[ans][i];
	}
	return v[ans];
}

int id, mdep;
int mxv[4000007], fa[4000007];
std::vector<int> v[17], son[4000007];

int f[67][17], g[67][67][17];

inline void predp(int n, int m){
	f[1][1] = g[1][1][1] = 0;
	for (int i = 2; i <= n; i++){
		f[i][1] = 1e9;
		for (int j = 1; j <= i; j++){
			g[i][j][1] = 1e9;
		}
	}
	for (int ap = 2; ap <= m; ap++){
		for (int i = 2; i <= n; i++){
			for (int j = 2; j <= i; j++){
				g[i][j][ap] = 1e9;
				for (int k = 1; k < i; k++){
					if (j - 1 <= i - k) g[i][j][ap] = std::min(g[i][j][ap], g[i - k][j - 1][ap] + f[k][ap]);
				}
			}
			f[i][ap] = f[i][ap - 1];
			for (int j = 2; j <= i; j++){
				f[i][ap] = std::min(f[i][ap], j * (j - 1) / 2 + g[i][j][ap - 1]);
			}
			g[i][1][ap] = f[i][ap];
		}
	}
}

int build(int l, int r, int dep){
	int cid = ++id;
	if (mdep < dep){
		mdep = dep;
		v[dep].clear();
	}
	v[dep].push_back(cid);
	if (l == r){
		mxv[cid] = l;
	} else if (dep >= 4 && r - l + 1 <= 60){
		int len = r - l + 1, ap = 12 - dep;
		for (int i = 2; i <= len; i++){
			if (f[len][ap] == i * (i - 1) / 2 + g[len][i][ap - 1]){
				int cur = l;
				while (i > 1){
					for (int j = 1; j < len; j++){
						if (i - 1 <= len - j && g[len][i][ap - 1] == g[len - j][i - 1][ap - 1] + f[j][ap - 1]){
							int cur_ = cur + j;
							fa[build(cur, cur_ - 1, dep + 1)] = cid;
							cur = cur_;
							len -= j;
							break;
						}
					}
					i--;
				}
				fa[build(cur, r, dep + 1)] = cid;
				break;
			}
		}
	} else {
		int cnt = pow(r - l + 1, 0.34), len = (r - l + 1) / cnt, rem = (r - l + 1) % cnt, cur = l;
		for (int i = 1; i <= cnt; i++){
			int nxt = cur + len + (i <= rem);
			fa[build(cur, nxt - 1, dep + 1)] = cid;
			cur = nxt;
		}
	}
	return cid;
}

int richest(int N, int T, int S){
	if (T == 1){
		std::vector<int> p;
		for (int i = 0; i < N; i++){
			p.push_back(i);
		}
		return onequery(p);
	}
	id = mdep = 0;
	predp(60, 8);
	build(0, N - 1, 1);
	for (int i = 1; i <= id; i++){
		son[i].clear();
	}
	for (int i = 2; i <= id; i++){
		son[fa[i]].push_back(i);
	}
	for (int i = mdep - 1; i >= 1; i--){
		std::vector<int> a, b, c;
		for (int j : v[i]){
			for (int k = 0; k + 1 < son[j].size(); k++){
				for (int l = k + 1; l < son[j].size(); l++){
					a.push_back(mxv[son[j][k]]);
					b.push_back(mxv[son[j][l]]);
				}
			}
		}
		c = ask(a, b);
		std::reverse(v[i].begin(), v[i].end());
		for (int j : v[i]){
			if (son[j].empty()) continue;
			if (son[j].size() == 1){
				mxv[j] = mxv[son[j][0]];
				continue;
			}
			int pos;
			for (int k = 0; k < son[j].size(); k++){
				refer[mxv[son[j][k]]] = k;
			}
			for (int k = son[j].size() - 2; k >= 0; k--){
				for (int l = son[j].size() - 1; l > k; l--){
					mx[k][l] = mx[l][k] = refer[c.back()];
					c.pop_back();
				}
			}
			pos = 0;
			for (int k = 1; k < son[j].size(); k++){
				pos = mx[pos][k];
			}
			mxv[j] = mxv[son[j][pos]];
		}
	}
	return mxv[1];
}