#include "richest.h"
#include<bits/stdc++.h>
using namespace std;
#define all(x) begin(x),end(x)
#define ran(x,l,r) begin(x)+l,begin(x)+(r+1)
#define F(i,a,b) for(int i=a,i##E=b;i<=i##E;i++)
#define UF(i,a,b) for(int i=a,i##E=b;i>=i##E;i--)
#define sz(x) int(x.size())
#define vec vector
template<typename T>
void operator+=(vec<T> &a,const T&b) {a.push_back(b);}
int R[]{500000,250000,125000,62500,20833,3472,183,1};
// std::vector <int> ask(std::vector <int> a, std::vector <int> b) {
//     return a;
// }
int richest(int N,int T,int S) {
    int n=N;
    if(N==1000) {
        vec<int> a,b;
        F(i,0,n-1) F(j,i+1,n-1) {
            a+=i,b+=j;
        } 
        vec<int> c(n);
        for(int x:ask(a,b)) c[x]++;
        F(i,0,n-1) if(c[i]==n-1) return i;
        return 1;
    }
    int now{N};
    vec<int> A;
    F(i,0,n-1) A+=i;
    for(int r:R) {
        vec<int> a,b;
        auto push=[&](vec<int> t) {
            for(int x:t) for(int y:t) if(x<y) a+=x,b+=y;
        };
        vec<int> V;
        F(i,1,r) V+=now/r;
        F(i,0,now%r-1) V[i]++;
        vec<int> NOT(n,1);
        for(int x:A) NOT[x]=0;
        vec<int> B,tmp;
        for(int x:A) {
            tmp+=x;
            if(sz(tmp)==V.back()) push(tmp),tmp={},V.pop_back();
        }
        vec<int> c=ask(a,b);
        F(i,0,sz(a)-1) NOT[a[i]^b[i]^c[i]]=1;
        F(i,0,n-1) if(!NOT[i]) B+=i;
        cerr<<r<<' '<<sz(B)<<endl;
        assert(sz(B)==r);
        swap(A,B);now=sz(A);
    } return A[0];
}
// int main() {richest(1000000,20,2000000);}