// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include"richest.h"
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define int long long
#define ull unsigned long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 1000006
#define inf 0x3f3f3f3f

ll f[10][maxn];
int pos[10][maxn],post[10][maxn];
bool bo;

void div(int k,int l,int r,int bl,int br){
	if(l>r||bl>br)return;
	int mid=l+r>>1;
	For(t,bl,br){
		ll B=mid/t;
		ll t2=mid%t,t1=t-t2;
		ll co=t1*(1ll*B*(B-1)/2)+t2*(1ll*B*(B+1)/2);
		co+=f[k-1][t];
		if(co<f[k][mid]){
			f[k][mid]=co;
			pos[k][mid]=B;
			post[k][mid]=t;
		}
	}
	div(k,l,mid-1,bl,post[k][mid]);
	div(k,mid+1,r,post[k][mid],br);
}
void init(){
	bo=1;
	int n=1000000;
	memset(f,63,sizeof f);
	f[0][1]=0;
	For(i,1,8) div(i,1,n,1,n);
}

int in[maxn];
int richest(int n,int T,int S){
	if(T==1 && n==1000 && S==499500){
		vi a,b;
		For(i,0,n-1) in[i]=0;
		For(i,0,n-1)For(j,i+1,n-1)a.pb(i),b.pb(j);
		vi c=ask(a,b); int p=0;
		For(i,0,SZ(c)-1){
			if(c[i]==a[i])++in[b[i]];
			else ++in[a[i]];
		}
		For(i,0,n-1)if(!in[i])return i;
		assert(0);
	}
	if(!bo) init();
	vi o;
	For(i,0,n-1) o.pb(i);
	int qcnt=8;
	while(SZ(o)>1){
		for(int x:o)in[x]=0;
		n=o.size();
		vi a,b;
		int t=post[qcnt][n]; --qcnt;
		int B=n/t;
		int t2=n%t,t1=t-t2;
		for(int l=0;l<n;){
			int add=0;
			if(t1)add=B,--t1;
			else add=B+1,--t2;
			int r=min(n-1,l+add-1);
			For(i,l,r)For(j,i+1,r)a.pb(o[i]),b.pb(o[j]);
			l=r+1;
		}
		vi c=ask(a,b);
		For(i,0,SZ(c)-1){
			if(c[i]==a[i])++in[b[i]];
			else ++in[a[i]];
		}
		vi o2;
		for(int x:o)if(!in[x])o2.pb(x);
		o=o2;
	}
	return o[0];
}
/*

*/