#include<bits/stdc++.h>
std::vector<int> ask(std::vector<int> a, std::vector<int> b);
using namespace std;
#define pb push_back
#define MT int TTT=R;while(TTT--)
#define pc putchar
#define R read()
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i>=b;i--)
#define m1(a,b) memset(a,b,sizeof a)
namespace IO
{
	inline int read()
	{
	    int x=0;
	    char ch=getchar();
	    bool f=0;
	    while(!isdigit(ch)){if(ch=='-') f=1;ch=getchar();}
	    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	    if(f) x=-x;
	    return x;    
	}
	template<typename T> inline void write(T x)
	{
	    if(x<0) pc('-'),x=-x;
	    if(x>9) write(x/10);
	    pc(x%10+'0');
	}
};
namespace math
{
	inline int gcd(int a,int b)
	{
		int az=__builtin_ctz(a),bz=__builtin_ctz(b),z=(az>bz)?bz:az,t;
	    b>>=bz;
	    while(a) a>>=az,t=a-b,b=a,az=__builtin_ctz(t<0?-t:t),a=t<0?-t:t;
	    return b<<z;
	}
	inline int qmi(int a,int b,int p)
	{
		int res=1;
		while(b)
		{
			if(b&1) res=res*a%p;
			a=a*a%p;
			b>>=1;
		}
		return res;
	}
	const int MAXN=2e6+10;
	int my_fac[MAXN],my_inv[MAXN];
	void init_binom(int mod)
	{
		my_fac[0]=1;fo(i,1,min(MAXN,mod)-1) my_fac[i]=my_fac[i-1]*i%mod;
		my_inv[min(MAXN,mod)-1]=qmi(my_fac[min(MAXN,mod)-1],mod-2,mod);rep(i,min(MAXN,mod)-2,0) my_inv[i]=my_inv[i+1]*(i+1)%mod;
	}
	int binom(int a,int b,int mod)
	{
		return my_fac[a]*my_inv[b]%mod*my_inv[a-b]%mod;
	}
};
using namespace IO;
using namespace math;

int tmp[]={0,1,183,3472,20832,62498,125000,250000,500000};
int flag[1000010];
int cnt[1000010];
int richest(int N,int T,int S)
{
	if(N==1000)
	{
		m1(cnt,0);
		vector<int> a,b,res;
		a.clear(),b.clear(),res.clear();
		fo(i,0,N-1) fo(j,i+1,N-1) a.pb(i),b.pb(j);
		res=ask(a,b);
		for(auto i:res) cnt[i]++;
		fo(i,0,N-1) if(cnt[i]==N-1) return i;
	}
	m1(flag,0);
	vector<int> now,a,b,res;
	fo(i,0,N-1) now.pb(i);
	rep(I,8,1)
	{
		a.clear(),b.clear(),res.clear();
		int x=N/tmp[I],y=N%tmp[I],pos=0;
		for(int i=1;i<=tmp[I]-y;i++,pos+=x) fo(j,pos,pos+x-1) fo(k,pos,j-1) a.pb(now[j]),b.pb(now[k]);
		for(int i=1;i<=y;i++,pos+=x+1) fo(j,pos,pos+x) fo(k,pos,j-1) a.pb(now[j]),b.pb(now[k]);
		res=ask(a,b);
		fo(i,0,(int)res.size()-1) (res[i]==a[i]?flag[b[i]]++:flag[a[i]]++);
		res.clear();
		for(auto i:now) if(!flag[i]) res.pb(i);
		now=res,N=now.size(),m1(flag,0);
	}
	return now[0];
}