//Linkwish's code
#include<bits/stdc++.h>
#include "richest.h"
#define endl '\n'
#define si static inline
#define mp make_pair
#define fi first
#define se second
using namespace std;typedef long long ll;typedef __int128 li;
typedef pair<int,int> pii;typedef pair<ll,ll> pll;typedef const int ci;
typedef const ll cl;const int iinf=INT_MAX;const ll linf=LLONG_MAX;
template<typename T>si bool gmax(T &x,const T y){if(x<y)return x=y,1;return 0;}
template<typename T>si bool gmin(T &x,const T y){if(y<x)return x=y,1;return 0;}

int n;

namespace S1{
	ci N=1005;
	int tot[N];
	si int solve(){
		memset(tot,0,sizeof tot);
		vector<int> a,b;
		for(int i=0;i<n;i++)
			for(int j=i+1;j<n;j++)
				a.push_back(i),b.push_back(j);
		vector<int> res=ask(a,b);
		for(int i=0;i<(int)res.size();i++)tot[res[i]]++;
		for(int i=0;i<n;i++)if(tot[i]==n-1)return i;
		return -1;
	}
}
namespace S2{

	ci N=1000005;
	
	int f[8]={500000,250000,125000,62496,20832,3472,183,1};
	int tot[N];
	si int solve(){
		vector<int> cur(n);iota(cur.begin(),cur.end(),0);
		for(int i=0;i<8;i++){
			int s=cur.size(),p=s/f[i],a=f[i]-s%f[i],b=f[i]-a;
			int k=0;
			vector<int> qa,qb;
			for(int j=0;j<a;j++,k+=p)
				for(int x=k;x<k+p;x++)
					for(int y=x+1;y<k+p;y++)
						qa.push_back(cur[x]),qb.push_back(cur[y]);
			for(int j=0;j<b;j++,k+=p+1)
				for(int x=k;x<=k+p;x++)
					for(int y=x+1;y<=k+p;y++)
						qa.push_back(cur[x]),qb.push_back(cur[y]);
			

			vector<int> res=ask(qa,qb);
			memset(tot,0,sizeof tot);
			for(int j:res)tot[j]++;

			vector<int> tmp;
			k=0;
			for(int j=0;j<a;j++,k+=p)
				for(int x=k;x<k+p;x++)
					if(tot[cur[x]]==p-1)
						tmp.push_back(cur[x]);
			for(int j=0;j<b;j++,k+=p+1)
				for(int x=k;x<=k+p;x++)
					if(tot[cur[x]]==p)
						tmp.push_back(cur[x]);

			cur.swap(tmp);
		}
		return cur[0];
	}
}
int richest(int N, int T, int S) {
	n=N;
	if(N<=1000)return S1::solve();
	else return S2::solve();
    return -1;
}