#include"richest.h"
#include<bits/stdc++.h>
using namespace std;
const int wk[15]={0,0,15,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];
    for(int i=0;i<N;i+=d) {
        int ed=(i+d<N?i+d:N);
        vector<int>nv(v.begin()+i,v.begin()+ed);
        Ask(nv,ed-i,1,a,b);
    }
    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>=9) return dfs(N,9,v);
}
//g++ grader.cpp richest.cpp -o richest -O2 -std=c++14 -static