#include "richest.h"

int richest(int N,int T,int S)
{
    if(N==1000)
    {
        std::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);
        auto c=ask(a,b);

        int res=0;
        for(int i=0,k=0;i<N;i++)
            for(int j=i+1;j<N;j++,k++)
                if((res==a[k]||res==b[k])&&res!=c[k])res=c[k];
        return res;
    }

    std::vector<int> a,b,c;
    for(int i=0;i<N;i++)c.push_back(i);

    while(c.size()>1)
    {
        int back=c.size()&1?c.back():0;
        std::vector<int>().swap(a),std::vector<int>().swap(b);
        for(int i=0;i+1<c.size();i+=2)a.push_back(c[i]),b.push_back(c[i+1]);
        c=ask(a,b);
        if(back)c.push_back(back);
    }

    return c[0];
}