#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,kkk[9]={1,183,3472,20833,62500,125000,250000,500000,1000000};
bool vis[N];
std::vector<int> ask(std::vector<int> a, std::vector<int> b);
std::vector<int> query(std::vector<int> a, std::vector<int> b){
    for(int i = 0;i<a.size();i++)a[i]--,b[i]--;
    auto c= ask(a,b);
    for(int i = 0;i<c.size();i++)c[i]++;
    return c;
}
int richest(int N, int T, int S) {
    n=N;
    if(T==1){
        vector<int>a,b;
        for(int i = 1;i<=n;i++){
            for(int j = i+1;j<=n;j++){
                a.push_back(i),b.push_back(j);
            }
        }
        auto c = query(a,b);
        for(int i = 1;i<=n;i++)vis[i]=1;
        for(int i = 0;i<a.size();i++){
            if(a[i]==c[i])vis[b[i]]=0;
            else vis[a[i]]=0;
        }
        for(int i = 1;i<=n;i++)if(vis[i])return i-1;
    }
    vector<int>a,b,c,d,e;
    for(int i = 1;i<=n;i++)d.push_back(i),vis[i]=1;
    for(int i = 8;i>=0;i--){
        if(kkk[i] >= n)continue;
        // cerr<<i<<endl;
        int now = n/kkk[i],qwq=n%kkk[i],lst=d.size()-1;
        for(int j = 1,w;j<=kkk[i];j++){
            w=now + (j<=qwq);
            e.clear();
            for(int k = 1;k<=w;k++)e.push_back(d[lst--]);
            for(int x1=0;x1<e.size();x1++){
                for(int x2=x1+1;x2<e.size();x2++)a.push_back(e[x1]),b.push_back(e[x2]);
            }
        }
        // cerr<<a.size()<<endl;
        c = query(a,b);
        for(int j = 0;j<a.size();j++){
            if(a[j]==c[j])vis[b[j]]=0;
            else vis[a[j]]=0;
        }
        e.clear();
        for(auto j : d)if(vis[j])e.push_back(j);
        d=e;
        n=kkk[i];
        a.clear(),b.clear();
    }
    return d.back()-1;
}