#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) {
    vector<int>vis(N,0);
    vector<int>a,b,ans;
    for(int i=0;i<N;i++)
        for(int j=i+1;j<N;j++)
            a.push_back(i),b.push_back(j);
    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 dfs(int N,int T,vector<int>v) {
    if(N==1) return v[0];
    if(T==1) return Ask(v,N);
    vector<int>dv;
    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);
        dv.push_back(Ask(nv,ed-i));
    }
    dfs(dv.size(),T-1,dv);
}

int richest(int N,int T,int S) {
    if(N==1000) {
        vector<int>vis(N,0);
        vector<int>a,b,ans;
        for(int i=0;i<N;i++)
            for(int j=i+1;j<N;j++)
                a.push_back(i),b.push_back(j);
        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]==i) vis[j]=1;
                    else vis[i]=1;
                    ++ij;
                }
        for(int i=0;i<N;i++) if(!vis[i]) return i;
    }
    if(T>=9) {
        vector<int>v(N);
        for(int i=0;i<N;i++) v.push_back(i);
        return dfs(N,T,v);
    }
}
//g++ grader.cpp richest.cpp -o richest -O2 -std=c++14 -static