//¸¡ÓÎÖ®ÈË Ò²ÕõÔú²»ÒÑÖ´×Å´æÔÚÏÂÈ¥
#include<bits/stdc++.h>
//#include "richest.h"
using namespace std;
#define NN 1000010
#define db long double
#define pii pair<int,int>
#define st first
#define ed second
#define mkp make_pair
#define pb push_back
#define eps 1e-9
#define mod 998244353
#define mod2 1000000007
#define bs 13131
#define bs2 131
#define INF 0x3f3f3f3f3f3f3f3f
#define il inline
#define vi vector<int>
#define ins insert
#define umap unordered_map
#define uset unordered_set
#define R(x) x.begin(),x.end()
#define B(x) x.begin()
#define E(x) x.end()
#define lb lower_bound
#define ub upper_bound
#define vi vector<int>
il int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int n,q,k;
struct edge{
	int y,nxt;
}e[NN];
int head[NN],tot,now[NN];
il void add(int x,int y){
	e[++tot]={y,head[x]};
	head[x]=tot;
}
vi ask(vi a,vi b);
int vis[NN];
il void reset(int n){
	tot=0;
	for(int i=0;i<n;i++)head[i]=now[i]=vis[i]=0;
}
int FL=0;
il int get(vi a){
	int p=a[0];
	while(head[p]){
		for(int &i=now[p];i;i=e[i].nxt){
//		if(FL)printf("%lld %lld\n",p,e[i].y);
			p=e[i].y;
			i=e[i].nxt;
			break;
		}
		if(!p)break;
	}
	return p;
}
il int solve1(){
	reset(n);
	vi a,b;
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++)
			a.pb(i),b.pb(j);
	vi op=ask(a,b);
	for(int i=0;i<op.size();i++){
		int A=a[i],B=b[i];
		if(op[i]==A)add(B,A);
		else add(A,B);
	}
	for(int i=0;i<n;i++)now[i]=head[i];
	a.clear();
	for(int i=0;i<n;i++)a.pb(i);
	return get(a);
}
int Q[9][NN],m[9];
il int solve2(){
	int cnt=0;
	for(int i=1;i<=8;i++)m[i]=0;
	for(int i=500000;i>=1;i--)Q[1][++m[1]]=2;
	for(int i=250000;i>=1;i--)Q[2][++m[2]]=2;
	for(int i=125000;i>=1;i--)Q[3][++m[3]]=2;
	for(int i=62500;i>=1;i--)Q[4][++m[4]]=2;
	for(int i=20832;i>=1;i--)Q[5][++m[5]]=3;Q[5][++m[5]]=4;	
	for(int i=3471;i>=1;i--)Q[6][++m[6]]=6;Q[6][++m[6]]=7;
	for(int i=5;i>=1;i--)Q[7][++m[7]]=18;
	for(int i=178;i>=1;i--)Q[7][++m[7]]=19;
	Q[8][++m[8]]=183;
	vector<int> x,y;
	for(int i=0;i<1000000;i++)x.pb(i);
	int sz=1000000;
	for(int k=1;k<=8;k++){
		sz=x.size();
		reset(sz);
		sort(R(x));
//		for(int i=1;i<x.size();i++){
//			if(x[i]==x[i-1])
//				puts("!!!!!!!!!!!!!!!!!!!!!!!!");
//		}
		int l=0;
		vi a,b,op;
		for(int p=1;p<=m[k];p++){
			int r=l+Q[k][p]-1;
			
			for(int i=l;i<r;i++)
				for(int j=i+1;j<=r;j++)
					a.pb(x[i]),b.pb(x[j]);
			l=r+1;
		}
		op=ask(a,b);
		cnt++;
		for(int i=0;i<op.size();i++){
			int A=a[i],B=b[i];
			if(op[i]==A)add(B,A);
			else add(A,B);
		}
		for(int i=0;i<n;i++)now[i]=head[i];
		l=0;
//	printf("*%lld\n",sz);
//		printf("%lld %lld\n",x[0],x[1]);
		for(int p=1;p<=m[k];p++){
			int r=l+Q[k][p]-1;
			if(k==3)FL=1;
			a.clear();
			for(int i=l;i<=r;i++)a.pb(x[i]);
			y.pb(get(a));
			l=r+1;
		}
		swap(x,y);
		y.clear();
	}
	return x[0];
}
int richest(int nn,int ttt,int sss){
	n=nn;
	if(n<=1000)return solve1();
	else return solve2();
}
/*
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;
}

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);
//        	for(int i=0;i<N;i++)cout << W[i] << " ";
//			puts("");
//			cout << r << endl;
            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;
        }
    }
}
*/