#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second 
#define all(x) x.begin(), x.end()

//1 183 3473 20834 62500
int richest(int n, int T, int S) {
    if (T==1) {
        vector<int> f,s;
        forn(i,n) forn(j,i) {f.pb(j); s.pb(i);}
        auto z = ask(f,s);
        vector<pi> cnt(n);
        forn(i,n) cnt[i].s=i;
        for(auto&x:z) cnt[x].f++;
        sort(all(cnt));
        return cnt[n-1].s;
    }
    vector<int> a; forn(i,n) a.pb(i);
    for(int it=0; it<4; ++it) {
        vector<int> f,s;
        for(int i=0; i<a.size(); i+=2) {
            f.pb(a[i]);
            s.pb(a[i+1]);
        }
        auto z = ask(f,s);
        a = z;
    }
    vector<int> cnt(n);
    for(int it=0; it<1; ++it) {
        vector<int> f,s;
        for(int i=0; i+3<a.size(); i+=3) {
            for(int x=0; x<3; ++x) {
                for(int y=x+1; y<3; ++y) {
                    f.pb(a[i+x]);
                    s.pb(a[i+y]);
                }
            }
        }
        auto z = ask(f,s);
        for(auto&x:z) cnt[x]++;
        vector<int> b;
        assert(a.size()%3==1);
        b.pb(a.back());
        forn(i,n) if (cnt[i]==2) b.pb(i);
        forn(i,n) cnt[i]=0;
        a=b;
    }
    for(int it=0; it<1; ++it) {
        vector<int> f,s;
        for(int i=0; i+6<a.size(); i+=6) {
            for(int x=0; x<6; ++x) {
                for(int y=x+1; y<6; ++y) {
                    f.pb(a[i+x]);
                    s.pb(a[i+y]);
                }
            }
        }
        int m=a.size();
        f.pb(a[m-2]);
        s.pb(a[m-1]);
        auto z = ask(f,s);
        for(auto&x:z) cnt[x]++;
        vector<int> b;
        assert(m%6==2);
        forn(i,n) if (cnt[i]==5) b.pb(i);
        forn(i,n) cnt[i]=0;
        b.pb(z.back());
        a=b;
    }
    for(int it=0; it<1; ++it) {
        vector<int> f,s;
        int m=a.size(), k=19;
        for(int i=0; i+k<a.size(); i+=k) {
            for(int x=0; x<k; ++x) {
                for(int y=x+1; y<k; ++y) {
                    f.pb(a[i+x]);
                    s.pb(a[i+y]);
                }
            }
        }
        int k2=m%k;
        for(int i=m-(m%k); i<m; i+=k) {
            for(int x=0; x<k2; ++x) {
                for(int y=x+1; y<k2; ++y) {
                    f.pb(a[i+x]);
                    s.pb(a[i+y]);
                }
            }
        }
        auto z = ask(f,s);
        for(auto&x:z) cnt[x]++;
        vector<int> b;
        forn(i,n) if (cnt[i]==k-1) b.pb(i);
        forn(i,n) cnt[i]=0;
        for(int i=z.size()-k2*(k2-1)/2; i<z.size(); ++i) ++cnt[z[i]];
        forn(i,n) if (cnt[i]==k2-1) b.pb(i);
        forn(i,n) cnt[i]=0;
        a=b;
    }
    for(int it=0; it<1; ++it) {
        vector<int> f,s;
        int k=a.size();
        for(int i=0; i<a.size(); i+=k) {
            for(int x=0; x<k; ++x) {
                for(int y=x+1; y<k; ++y) {
                    f.pb(a[i+x]);
                    s.pb(a[i+y]);
                }
            }
        }
        auto z = ask(f,s);
        for(auto&x:z) cnt[x]++;
        vector<int> b;
        forn(i,n) if (cnt[i]==k-1) b.pb(i);
        forn(i,n) cnt[i]=0;
        a=b;
    }
    return a[0];
}