#include "richest.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;

int richest(int N, int T, int S) {
    vector<int> arr={500000,250000,125000,62496,20832,3472,183,1};
    if(N==1000)arr={1};
    vector<int> now(N);
    iota(all(now),0);
    rep(i,arr.size()) {
        vector<vector<int>> ques(arr[i]);
        rep(j,now.size()) {
            ques[j%arr[i]].emplace_back(now[j]);
        }
        vector<int> a,b;
        rep(j,arr[i]) {
            rep(k,ques[j].size()) {
                rep(l,k) {
                    a.emplace_back(ques[j][k]);
                    b.emplace_back(ques[j][l]);
                }
            }
        }
        vector<int> c=ask(a,b);
        vector<int> nxt(arr[i]);
        int cnt=0;
        rep(j,arr[i]) {
            int mx=0;
            rep(k,ques[j].size()) {
                rep(l,k) {
                    if(l==mx) {
                        if(c[cnt]==a[cnt]) {
                            mx=k;
                        }
                    }
                    cnt++;
                }
            }
            nxt[j]=ques[j][mx];
        }
        swap(now,nxt);
    }
    return now[0];
}