#include <bits/stdc++.h>
#include "richest.h"
using namespace std;
std::vector <int> ask(std::vector <int> a, std::vector <int> b);
int rfs[1005][1005];
void Div2(vector < int >& now , int lim = 7) {
    vector < int > a , b , c;
        int sig = -1;
        if(now.size() & 1) {
            sig = now.back();
        }
        for(int i = 0 ; i + 1 < now.size() ; i += 2) {
            a.push_back(now[i]);
            b.push_back(now[i + 1]);
        }c = ask(a , b);
        if(~sig) c.push_back(sig);
    now = c;
}
void Div(vector < int > &now , int p , int x) {
    vector < int > a , b , c , sig , nxt;
        while(now.size() % p) {
            sig.push_back(now.back()); now.pop_back();
        }
        for(int i = 0 ; i + p - 1 < now.size() ; i += p) {
            for(int j = i ; j < i + p ; j++) {
                for(int k = j + 1 ; k < i + p; k++) {
                    a.push_back(now[j]);
                    b.push_back(now[k]);
                }
            }
        }
        for(int i = 0 ; i < x ; i++) {
            for(int j = i + 1 ;j < x ; j++) {
                a.push_back(now[i]);
                b.push_back(now[j]);
            }
        }
        c = ask(a , b);
        int id = 0;
        for(int i = 0 ; i + p - 1 < now.size() ; i += p) {
            int ans = 0 , cnt = 0;
            map < int , int > mp;
            for(int j = i ; j < i + p ; j++) {
                for(int k = j + 1 , u ; k < i + p ; k++) {
                    u = c[id++];
                    mp[u]++;
                    if(mp[u] > cnt) {
                        cnt = mp[u];
                        ans = u;
                    }
                }
            }
            nxt.push_back(ans);
        }int ans = 0 , cnt = 0;map < int , int > mp;
        for(int i = 0 , u ; i < x ; i++) {
            for(int j = i + 1 ; j < x  ; j++) {
                u = c[id++];
                mp[u]++;
                if(mp[u] > cnt) {
                    cnt = mp[u];
                    ans = u;
                }
            }
        }nxt.push_back(ans);
    now = nxt;
    for(int i = x ; i < sig.size() ; i++) {
        now.push_back(sig[i]);
    }
}
int richest(int N , int T , int S) { 
    int cnt = 0;
    if(N == 1000) {
        vector < int > a , b , c;
       
        for(int i = 0 ; i < N ; i++) {
            for(int j = i + 1 ; j < N ; j++) {
                a.push_back(i);
                b.push_back(j);
                rfs[i][j] = cnt++;
            }
        }c = ask(a , b);
        int ans = 0;
        for(int i = 1 ; i < N ; i++) {
            int u = i , v = ans;
            if(u > v) swap(u , v);
            ans = c[rfs[u][v]];
        }return ans;
    }   
    vector < int > now;
    now.resize(N , 0);
    for(int i = 0 ; i < N ; i++) now[i] = i;
    Div(now , 2 , 1);
    Div(now , 2 , 1);
    Div(now , 2 , 1);
    Div(now , 2 , 1);
    // Div(now , 5);
    Div(now , 3 , 2);
    Div(now , 6 , 2);
    Div(now , 19 , 15);
    vector < int > a , b , c;
    cerr << now.size() << endl;
    for(int i = 0 ; i < now.size() ; i++) {
        for(int j = i + 1 ; j < now.size() ; j++) {
            // if(now[i] > now[j]) swap(now[i] , now[j])
            a.push_back(now[i]);
            b.push_back(now[j]);
            rfs[i][j] = cnt++;
        }
    }c = ask(a , b);
    int ans = now.size() - 1;
    for(int i = 0 ; i < now.size() - 1 ; i++) {
        int u = i , v = ans;
        if(u > v) swap(u , v);
        ans = c[rfs[u][v]] == now[u] ? u : v;
    }
    return now[ans];
}
/*
g++ grader.cpp 2.cpp -o 2 -O2 -std=c++14 -static
1000000 20 2000000 29091473
1000000
1 500000 500000
3 125000 125000

333334 666666
666666
111112 222224
888888
37038   
962962
115569
*/