#include"richest.h"
#include<bits/stdc++.h>
using namespace std;
const int wk[15]={0,0,19,6,3,2,2,2,2,2};

inline int Ask(vector<int>&v,int N,bool o,vector<int>&a,vector<int>&b) {
    vector<int>vis(N,0),ans;
    for(int i=0;i<N;i++)
        for(int j=i+1;j<N;j++) 
            a.push_back(v[i]),b.push_back(v[j]);
    if(o) return 0;
    ans=ask(a,b);
    int ij=0;
    for(int i=0;i<N;i++)
        for(int j=i+1;j<N;j++)
        {
            if(ans[ij]==v[i]) vis[j]=1;
            else vis[i]=1;
            ++ij;
        }
    for(int i=0;i<N;i++) if(!vis[i]) return v[i];
}

int rev[1000002];
int dfs(int N,int T,vector<int>v) {
    if(N==1) return v[0];
    if(T==1) {
        vector<int>a,b;
        return Ask(v,N,0,a,b);
    }
    vector<int>dv,a,b,ans;
    int d=wk[T];
    int ct=N/d;
    vector<int>s;
    for(int i=1;i<=ct;i++) s.push_back(d);
    if(ct*d<N) s.push_back(N-ct*d);
    while(s.size()>=2&&s[s.size()-2]-s.back()>1) {
        for(int id=s.size()-2;id>=0;id--)
            if(s[id]-s.back()<=1) break;
            else --s[id],++s[s.size()-1];
    }
    for(int i=0,j=0;j<s.size();j++) {
        vector<int>nv(v.begin()+i,v.begin()+i+s[j]);
        Ask(nv,s[j],1,a,b); i+=s[j];
    }
    for(int i=0;i<N;i++) rev[v[i]]=i;
    vector<int>vis(N,0);
    ans=ask(a,b);
    for(int i=0;i<(int)ans.size();i++) {
        if(ans[i]==a[i]) vis[rev[b[i]]]=1;
        else vis[rev[a[i]]]=1;
    }
    for(int i=0;i<N;i++) if(!vis[i]) dv.push_back(v[i]);
    return dfs(dv.size(),T-1,dv);
}

int richest(int N,int T,int S) {
    vector<int>v(N);
    for(int i=0;i<N;i++) v[i]=i;
    if(N==1000) return dfs(N,T,v);
    if(T>=8) return dfs(N,8,v);
}
//g++ grader.cpp richest.cpp -o richest -O2 -std=c++14 -static