#include<bits/stdc++.h>
#include "richest.h"
using namespace std;
inline int rd() {
    int s=0,m=0;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
    while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return m?-s:s;
}
int fl[1000005],mp[10]={0,1,183,3472,20832,62498,125000,250000,500000};
int richest(int N,int T,int S) {
    memset(fl,0,sizeof(fl));vector<int> now,a,b,ret;
    for(int i=0;i<N;i++) now.push_back(i);
    for(int ii=8;ii>=1;ii--) {
        a.clear(),b.clear(),ret.clear();
        int x=N/mp[ii],y=N%mp[ii],pos=0;
        for(int i=1;i<=mp[ii]-y;i++,pos+=x) for(int j=pos;j<pos+x;j++) for(int k=pos;k<j;k++)
            a.push_back(now[j]),b.push_back(now[k]);
        for(int i=1;i<=y;i++,pos+=x+1) for(int j=pos;j<=pos+x;j++) for(int k=pos;k<j;k++)
            a.push_back(now[j]),b.push_back(now[k]);
        ret=ask(a,b);for(int i=0;i<ret.size();i++) (ret[i]==a[i]?fl[b[i]]++:fl[a[i]]++);
        ret.clear();for(int i:now) if(!fl[i]) ret.push_back(i);
        now=ret;N=now.size();memset(fl,0,sizeof(fl));
    }
    return now[0];
}