#include<bits/stdc++.h>
#include "richest.h"
using namespace std;
mt19937 rd(5384);
int rg(int l,int r){return rd()%(r-l+1)+l;}
int slv(int n,vector<int>d) {
    int m=d.size();
    vector<int>a,b,ct(n);
    for(int i=0;i<m;i++)for(int j=i+1;j<m;j++)a.push_back(d[i]),b.push_back(d[j]);
    vector<int>c=ask(a,b);
    for(int i:c)ct[i]++;
    for(int i=0;i<n;i++)if(ct[i]==m-1)return i;
}
int richest(int n,int T,int S) {
    vector<int>a(n),del(n);
    iota(a.begin(),a.end(),0);
    if(T==1)return slv(n,a);
    while(a.size()>100000) {
        vector<int>qa,qb,qc,na,del(a.size());
        for(int i=0;i+1<a.size();i+=2)qa.push_back(a[i]),qb.push_back(a[i+1]);
        qc=ask(qa,qb);
        for(int i=0;i<qc.size();i++)if(qc[i]==qa[i])del[i*2+1]=1;else del[i*2]=1;
        for(int i=0;i<a.size();i++)if(!del[i])na.push_back(a[i]);
        a=na;
    }
    while(a.size()>10000) {
        int m=a.size();
        vector<int>qa,qb,qc,na;
        for(int i=0;i<m;i++)qa.push_back(a[i]),qb.push_back(a[(i+1)%m]);
        qc=ask(qa,qb);
        for(int i=0;i<qc.size();i++)if(qc[i]==qa[i])del[qb[i]]=1;else del[qa[i]]=1;
        for(int i:a)if(!del[i])na.push_back(i);else del[i]=0;   
        a=na;
    }
    while(a.size()>400) {
        int m=a.size();
        vector<int>qa,qb,qc,na;
        for(int i=0;i<m;i++)qa.push_back(a[i]),qb.push_back(a[(i+1)%m]);
        for(int i=0;i<m;i+=2)qa.push_back(a[i]),qb.push_back(a[(i+2)%m]);
        qc=ask(qa,qb);
        for(int i=0;i<qc.size();i++)if(qc[i]==qa[i])del[qb[i]]=1;else del[qa[i]]=1;
        for(int i:a)if(!del[i])na.push_back(i);else del[i]=0;   
        a=na;
    }
    cerr<<a.size()<<'\n';
    // return a[0];
    return slv(n,a);
}