#include "richest.h"
#include<bits/stdc++.h>
using namespace std;
/*
static int N, T, S, r, t, s;
static vector<int> W;
vector<int> ask(vector<int> i, vector<int> j) {
    ++t;
    if (t > T)
        throw string("Too many queries");
    if (i.size() != j.size())
        throw string("Invalid query: i and j must have the same size");
    int m = i.size();
    s += m;
    if (s > S)
        throw string("Too many total elements in queries");
    vector<int> res(m);
    for (int k = 0; k < m; k++) {
        if (i[k] < 0 || i[k] >= N || j[k] < 0 || j[k] >= N)
            throw string("Invalid query: index out of bounds");
        res[k] = W[i[k]] > W[j[k]] ? i[k] : j[k];
    }
    return res;
}
*/
vector<int> a,b,c,d;
int cnt[1000005],mp[10]={0,1,183,3472,20833,62500,125000,250000,500000};
void add(int x,int y){
	a.push_back(x),b.push_back(y);
}
void clear(){
	for(int i=0;i<1000000;i++) cnt[i]=0;
}
int richest(int n,int T,int S){
	if(n==1000){
		a.clear(),b.clear(),c.clear();
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				add(i,j);
			}
		}
		c=ask(a,b);
		clear();
		for(int i=0;i<c.size();i++){
			cnt[a[i]+b[i]-c[i]]++; 
		}
		int id=0;
		for(int i=0;i<n;i++){
			if(cnt[i]==0) id=i;
		}
		return id;
	}else{
		clear();
		c.clear();
		for(int i=0;i<n;i++) c.push_back(i);
		for(int ii=8;ii>=1;ii--){
			a.clear(),b.clear(),d.clear();
			int x=n/mp[ii],y=n%mp[ii],pos=0;
	        for(int i=1;i<=mp[ii]-y;i++,pos+=x){
	        	for(int j=pos;j<pos+x;j++){
	        		for(int k=pos;k<j;k++){
	        			add(c[j],c[k]);
					}
				}
			}
	        for(int i=1;i<=y;i++,pos+=x+1){
	        	for(int j=pos;j<=pos+x;j++){
	        		for(int k=pos;k<j;k++){
	        			add(c[j],c[k]);
					}
				}
			}
			d=ask(a,b);
			for(int i=0;i<d.size();i++){
				cnt[a[i]+b[i]-d[i]]++;
			}
			d.clear();
			for(int i:c){
				if(cnt[i]==0) d.push_back(i);
			}
			c=d;
			n=c.size();
			clear();
		}
		return c[0];
	}
	return 1;
}
/*
constexpr int Sub2_score = 85;

signed main() {
    int R;
    cin >> N >> T >> S >> R;
    if (N <= 0 || T < 0 || S < 0 || R < 0) {
        cerr << "Invalid input for N, T, S or R" << endl;
        return 1;
    }
    mt19937_64 rng(R);
    W.resize(N);
    bool hasWrong = false;
    int maxt = 0, maxs = 0;
    for (int _ = 0; _ < 10; _++) {
        iota(W.begin(), W.end(), 0);
        shuffle(W.begin(), W.end(), rng);
        int answer = max_element(W.begin(), W.end()) - W.begin();
        try {
            r = -1; t = 0; s = 0;
            r = richest(N, T, S);
            if (r != answer)
                throw string("Wrong Answer");
            cout << r << ' ' << t << ' ' << s << " Correct (pretest)" << endl;
        } catch (const string& msg) {
            hasWrong = true;
            cout << r << ' ' << t << ' ' << s << ' ' << msg << endl;
        }
        maxt = max(maxt, t);
        maxs = max(maxs, s);
    }
    if (N == 1000 && T == 1 && S == 499500) {
        if (hasWrong) {
            cout << "Wrong Case 1, score: 0 / " << (100 - Sub2_score) << endl;
        } else {
            cout << "Correct (pretest) Case 1, score: " << (100 - Sub2_score) << " / " << (100 - Sub2_score) << endl;
        }
    } else if (N == 1000000 && T == 20 && S == 2000000) {
        if (hasWrong) {
            cout << "Wrong Case 2, score: 0 / " << Sub2_score << endl;
        } else {
            double ft = 1;
            if (maxt > 8)
                ft -= sqrt(maxt - 8) / 4;
            double gs = 1;
            if (maxs > 1099944) {
            	if (maxs < 1100044)
            		gs -= log10(maxs - 1099943) / 6;
            	else
            		gs -= 1.0 / 3 + pow(maxs - 1100043, 1.0 / 2) / 1500;
			}
            cout
                << (ft * gs >= 1 ? "Correct" : "Partially correct")
                << " (pretest) Case 2, score: "
                << to_string(int(Sub2_score * ft * gs))
                << " / " << Sub2_score;
        }
    } else {
        if (hasWrong) {
            cout << "Wrong" << endl;
        } else {
            cout << "Correct" << endl;
        }
    }
}
*/