#include "richest.h"
#include<bits/stdc++.h>
using namespace std;
int a[10]={1000000,500000,250000,125000,62500,20833,3472,183,1};
int col[1000005];
vector<int> v[1000005];
bitset<1000005> ok,vis;
int richest(int N, int T, int qwq) {
	vector<int> S;
	if(N==1000)
	{
		a[0]=1000;
		a[1]=1;
	}
	for(int i=1;i<=N;i++) S.push_back(i-1);
	for(int i=1;i<=(N==1000?1:8);i++)
	{
		int w=a[i-1]/a[i],C1=a[i-1]%a[i],C0=a[i]-C1;
		int nw=0,C=0;
		for(int i=0;i<=N;i++) v[i].clear();
		for(int i=1;i<=C1;i++)
		{
			++C;
			for(int j=0;j<=w;j++)
				v[C].push_back(S[nw++]);
		}
		for(int i=1;i<=C0;i++)
		{
			++C;
			for(int j=1;j<=w;j++)
				v[C].push_back(S[nw++]);
		}
		vector<int> v1,v2;
		set<int> ss;
		vis.reset();
		for(int i=1;i<=C;i++)
		{
			for(auto x:v[i])
			{
				for(auto y:v[i])
				{
					if(x==y) break;
					v1.push_back(x),v2.push_back(y);
					vis[x]=vis[y]=1;
				}
			}
		}
		vector<int> V=ask(v1,v2);
		ok.reset();
		for(int i=0;i<v1.size();i++)
		{
			ok[v1[i]+v2[i]-V[i]]=1;
		}
		S.clear();
		for(int i=0;i<N;i++)
			if(!ok[i]&&vis[i]) S.push_back(i);
//		for(auto t:ss) S.push_back(t);
	}
//	cout << S.size() << "\n";
    return S[0];
}