#include "richest.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
/*
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,sy,s1;
int cnt[1000010];
int richest(int n, int T, int S) {
	if(n<=1000){
		for(int i=0;i<n;i++) cnt[i]=0;
		a.clear(),b.clear();
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				a.pb(i),b.pb(j);
			}
		}
		sy=ask(a,b);
		for(int i:sy){
			cnt[i]++;
		}
		int mx=0,id=0;
		for(int i=0;i<n;i++){
			if(cnt[i]>mx){
				mx=cnt[i];
				id=i;
			}
		}
		return id;
	}else{
		sy.clear();
		for(int i=0;i<n;i++) sy.push_back(i);
		int sz,id=0;
		for(int _=1;_<=6;_++){
			a.clear(),b.clear();
			sz=sy.size();
			for(int i=0;i<sy.size()-1;i+=2){
				int x1=sy[i],x2=sy[i+1];
				id=i+2;
				a.pb(x1),b.pb(x2);
			}
			s1.clear();
			for(int i=id;i<sz;i++) s1.pb(sy[i]);
			sy.clear();
			sy=ask(a,b);
			for(int i=0;i<s1.size();i++) sy.pb(s1[i]);
		}
	//	cout<<"sz_of_zy "<<sy.size()<<endl;
		a.clear(),b.clear();
		id=0;
		for(int i=0;i<sy.size()-3;i+=4){
			int x1=sy[i],x2=sy[i+1],x3=sy[i+2],x4=sy[i+3];
			a.pb(x1),b.pb(x2);
			a.pb(x1),b.pb(x3);
			a.pb(x1),b.pb(x4);
			a.pb(x2),b.pb(x3);
			a.pb(x2),b.pb(x4);
			a.pb(x3),b.pb(x4);
			id=i+4;
		}
		sz=sy.size();
		s1.clear();
		for(int i=id;i<sz;i++) s1.pb(sy[i]);
		sy.clear();
		sy=ask(a,b);
		for(int i=0;i<n;i++) cnt[i]=0;
		for(int i=0;i<sy.size();i++){
			cnt[sy[i]]++;
		}
		sy.clear();
		for(int i=0;i<n;i++){
			if(cnt[i]==3) sy.pb(i);
		}
		for(int i=0;i<s1.size();i++) sy.pb(s1[i]);
		a.clear(),b.clear();
	//	cout<<"sy "<<s1.size()<<" "<<sy.size()<<endl;
		for(int i=0;i<sy.size()-20;i+=21){
			for(int j=0;j<21;j++){
				for(int k=j+1;k<21;k++){
					a.pb(sy[i+j]);
					b.pb(sy[i+k]);
				}
			}
			id=i+21;
		}
		sz=sy.size();
		s1.clear();
		for(int i=id;i<sz;i++) s1.pb(sy[i]);
		sy.clear();
		sy=ask(a,b);
		for(int i=0;i<n;i++) cnt[i]=0;
		for(int i=0;i<sy.size();i++){
			cnt[sy[i]]++;
		}
		sy.clear();
		for(int i=0;i<n;i++){
			if(cnt[i]==20) sy.pb(i);
		}
		for(int i=0;i<s1.size();i++) sy.pb(s1[i]);
		for(int i=0;i<n;i++) cnt[i]=0;
		a.clear(),b.clear();
		for(int i=0;i<sy.size();i++){
			for(int j=i+1;j<sy.size();j++){
				a.pb(sy[i]);
				b.pb(sy[j]);
			}
		}
		sy=ask(a,b);
		int mx=0;
		id=0;
		for(int i=0;i<sy.size();i++){
			cnt[sy[i]]++;
		}
		for(int i=0;i<n;i++){
			if(cnt[i]>mx){
				mx=cnt[i];
				id=i;
			}
		}
		return id;
	}
}
/*
constexpr int Sub2_score = 85;

int 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;
        }
    }
}*/