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

using namespace std;

int zans;

int llw(vector<int> tp){
    int n = tp.size();
    vector<int> a, b;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < i; j++){
            a.push_back(i);
            b.push_back(j);
        }
    }
    vector<int> c = ask(a, b);
    vector<bool> d(n, 1);
    int ccnt = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < i; j++){
            d[i^j^c[ccnt++]] = 0;
        }
    }
    for(int i = 0; i < n; i++){
        if(d[i]){
            return i;
        }
    }
}

int cl[9] = {0, 500000, 250000, 125000, 62500, 20833, 3472, 182, 1};

void doit(int o, vector<int> &tp){
    // if(o == 8){
    //     zans = llw(tp);
    //     return ;
    // }
    int n = tp.size();
    // printf("doit(%d, %d)\n", o, n);
    vector<vector<int> > fz(cl[o]);
    for(int i = 0; i < n; i++){
        fz[i%cl[o]].push_back(tp[i]);
    }
    vector<int> nxt;
    vector<int> a, b;
    for(int k = 0; k < cl[o]; k++){
        int m = fz[k].size();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < i; j++){
                a.push_back(fz[k][i]);
                b.push_back(fz[k][j]);
            }
        }
    }
    vector<int> c = ask(a, b);
    int ccnt = 0;
    vector<bool> d(1000000, 1);
    for(int k = 0; k < cl[o]; k++){
        int m = fz[k].size();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < i; j++){
                // printf("%d %d %d\n", fz[k][i], fz[k][j], c[ccnt++]);
                d[fz[k][i]^fz[k][j]^c[ccnt++]] = 0;
            }
        }
    }
    for(int i = 0; i < n; i++){
        if(d[tp[i]]){
            nxt.push_back(tp[i]);
        }
    }
    if(o == 8){
        zans = nxt[0];
    }else{
        doit(o+1, nxt);
    }
}

int richest(int N, int T, int S) {
    vector<int> tp;
    for(int i = 0; i < N; i++){
        tp.push_back(i);
    }
    if(N == 1000){
        return llw(tp);
    }

    doit(1, tp);

    return zans;
}