#include "richest.h"
#include <bits/stdc++.h>
// #include "grader.cpp"

using namespace std;

const int maxn=1e6+5;

int bg[maxn];
int f[8]={2,2,2,2,3,6,19,183};

int richest(int n,int T,int S) {
    if(T==1) {
        vector<int> a, b, c;
        for(int i=0;i<n;i++) {
            bg[i]=a.size()-1;
            for(int j=i+1;j<n;j++) {
                a.push_back(i);
                b.push_back(j);
            }
        }
        c=ask(a,b);
        int x=0;
        for(int i=1;i<n;i++) {
            if(c[bg[x]+i-x]==x) ;
            else x=i;
        }
        return x;
    }
    vector<int> vec, vec2;
    for(int i=0;i<n;i++) vec.push_back(i);
    for(int p=0;p<8;p++) {
        int v=f[p];
        n=vec.size();
        if(v==2) {
            if(n&1) vec2.push_back(vec.back()), vec.pop_back(), --n;
            vector<int> a,b,c;
            for(int i=0;i<n;i+=2) {
                a.push_back(vec[i]);
                b.push_back(vec[i+1]);
            }
            c=ask(a,b);
            vec=vec2, vec2.clear();
            for(auto x:c) vec.push_back(x);
        }else {
            vector<int> a,b,c;
            for(int i=0;i<n;i+=v) {
                int v2=min(v,n-i);
                for(int j=i;j<i+v2;j++) {
                    bg[j]=a.size()-1;
                    for(int j2=j+1;j2<i+v2;j2++) {
                        a.push_back(vec[j]);
                        b.push_back(vec[j2]);
                    }
                }
            }
            c=ask(a,b);
            for(int i=0;i<n;i+=v) {
                int v2=min(v,n-i);
                int x=i;
                for(int j=i+1;j<i+v2;j++) {
                    if(c[bg[x]+j-x]==vec[x]) ;
                    else x=j;
                }
                vec2.push_back(vec[x]);
            }
            vec=vec2, vec2.clear();
        }
    }
    return vec[0];
}