#include <bits/stdc++.h>
#include "richest.h"
using namespace std;
vector<int>Kto1={2,2,2,2,3,6,19,183};
vector<int>Kto2={0,0,0,3,0,0,18,0};
vector<int>Ile= {0,0,0,8,0,0,4,0};
bool CzyJestGit[1000000];
int richest(int n, int T, int S)
{
    if(n==1000)
    {
        for(int i=0;i<n;i++)
        {
            CzyJestGit[i]=1;
        }
        vector<int>A,B;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                A.push_back(i);
                B.push_back(j);
            }
        }
        vector<int>W=ask(A,B);
        for(int i=0;i<A.size();i++)
        {
            if(W[i]==A[i])
            {
                CzyJestGit[B[i]]=0;
            }
            else
            {
                CzyJestGit[A[i]]=0;
            }
        }
        for(int i=0;i<n;i++)
        {
            if(CzyJestGit[i])
            {
                return i;
            }
        }
    }
    vector<int>Kand;
    for(int i=0;i<n;i++)
    {
        Kand.push_back(i);
    }
    for(int I=0;I<8;I++)
    {
        if(Kand.size()==1){break;}
        for(int u : Kand)
        {
            CzyJestGit[u]=1;
        }
        vector<vector<int>>U;
        for(int i=1;i<=Ile[I];i++)
        {
            vector<int>Temp;
            if(Kand.size()<Kto2[I]){break;}
            for(int j=1;j<=Kto2[I];j++)
            {
                Temp.push_back(Kand.back());
                Kand.pop_back();
            }
            U.push_back(Temp);
        }
        while(Kand.size()>=Kto1[I])
        {
            vector<int>Temp;
            for(int j=1;j<=Kto1[I];j++)
            {
                Temp.push_back(Kand.back());
                Kand.pop_back();
            }
            U.push_back(Temp);
        }
        if(Kand.size()>0)
        {
            U.push_back(Kand);
            Kand.clear();
        }
        vector<int>A,B;
        for(vector<int>Temp : U)
        {
            for(int a=0;a<Temp.size();a++)
            {
                for(int b=a+1;b<Temp.size();b++)
                {
                    A.push_back(Temp[a]);
                    B.push_back(Temp[b]);
                }
            }
        }
        vector<int>W=ask(A,B);
        for(int i=0;i<A.size();i++)
        {
            if(W[i]==A[i])
            {
                CzyJestGit[B[i]]=0;
            }
            else
            {
                CzyJestGit[A[i]]=0;
            }
        }
        for(int i=0;i<n;i++)
        {
            if(CzyJestGit[i])
            {
                Kand.push_back(i);
            }
        }
    }
    return Kand[0];
}