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

// std::vector<int> ask(std::vector<int> a,std::vector<int> b);

std::vector<int> p,q,r;
int a[1005][1005];
int f[8]={500000,250000,125000,62500,20833,3472,183,1};
std::vector<int> g[1000005];
int b[1000005],cnt;

int richest(int n,int t,int s){
    if(n==1000){
        p.clear(); q.clear();
        memset(a,0,sizeof(a));
        for(int i=0;i<=n-1;i++){
            for(int j=i+1;j<=n-1;j++){
                p.push_back(i); q.push_back(j);
            }
        }
        p=ask(p,q);
        int cnt=0;
        for(int i=0;i<=n-1;i++){
            for(int j=i+1;j<=n-1;j++){
                a[p[cnt]][i+j-p[cnt]]=1;
                cnt++;
            }
        }
        for(int i=0;i<=n-1;i++){
            int cnt=0;
            for(int j=0;j<=n-1;j++){
                cnt+=a[i][j];
            }
            if(cnt==n-1){
                return i;
            }
        }        
    }else{
        for(int i=0;i<=n-1;i++){
            b[i]=1;
        }
        for(int i=0;i<=7;i++){
            int sz=f[i];
            for(int j=0;j<=sz-1;j++){
                g[j].clear();
            }
            p.clear(); q.clear();
            cnt=-1;
            for(int j=0;j<=n-1;j++){
                if(!b[j]) continue;
                cnt++; cnt%=sz;
                g[cnt].push_back(j);
            }
            for(int j=0;j<=sz-1;j++){
                for(int x=0;x<g[j].size();x++){
                    for(int y=x+1;y<g[j].size();y++){
                        p.push_back(g[j][x]);
                        q.push_back(g[j][y]);
                    }
                }
            }
            r=ask(p,q);
            for(int i=0;i<r.size();i++){
                b[p[i]+q[i]-r[i]]=0;
            }
        }
        for(int i=0;i<=n-1;i++){
            if(b[i]){
                return i;
            }
        }
    }

    return 0;
}