#include<bits/stdc++.h>
#include"soul.h"
#define IL inline
#define reg register
#define N 50050
std::mt19937 rnd((unsigned long long)(new char));

int n;

IL bool check(reg int u,std::vector<int>A)
{
    reg int x=0,c=0;
    for(auto v:A)
    {
        if(!c){x=v,c=1; continue;}
        if(ask(u,x,v)==u)--c;
        else ++c;
    }
    c=0;
    for(auto v:A)c+=ask(u,x,v)!=u;
    return c<=n/2;
}

int pu,pv;

int dc(std::vector<int>P,std::vector<int>Q,reg int prefix,reg int suffix)
{
    reg int x=P[rnd()%P.size()],pre=prefix,suf=suffix;
    std::vector<int>Pl,Pr,Ql,Qr,sons;
    for(auto y:P)if(y!=x)
    {
        if(ask(pu,y,x)==y)++pre,Pl.push_back(y);
        else ++suf,Pr.push_back(y);
    }
    for(auto y:Q)
    {
        bool lhs=ask(pv,y,x)==x,rhs=ask(pu,y,x)==x;
        if(lhs&&!rhs)Ql.push_back(y),++pre;
        if(rhs&&!lhs)Qr.push_back(y),++suf;
        if(lhs&&rhs)sons.push_back(y);
    }
    if(pre<=n/2&&suf<=n/2)return check(x,sons)?x:0;
    if(pre>n/2)return dc(Pl,Ql,prefix,suf+sons.size()+1);
    return dc(Pr,Qr,pre+sons.size()+1,suffix);
}

int find(reg int u,reg int v)
{
    pu=u,pv=v;
    std::vector<int>P,Q;
    for(reg int i=1;i<=n;++i)
        if(ask(u,v,i)==i)P.push_back(i);
        else Q.push_back(i);
    return dc(P,Q,0,0);
}

int centroid(reg int id,reg int nn,reg int m)
{
    n=nn;
    if(n==3)return ask(1,2,3);
    if(id==3||id==5) // case: line
    {
        reg int x=1,y=2;
        for(reg int i=3,d;i<=n;++i)
        {
            d=ask(x,y,i);
            if(x==d)x=i;
            if(y==d)y=i;
        }
        static int p[N];
        p[m=1]=x;
        for(reg int i=1;i<=n;++i)if(i!=x)p[++m]=i;
        std::nth_element(p+2,p+n/2+1,p+n+1,[&](reg int a,reg int b){return ask(x,a,b)==a;});
        return p[n/2+1];
    }
    while(1)
    {
        reg int x=rnd()%n+1,y=rnd()%n+1,I=find(x,y);
        if(I)return I;
    }
}

// g++ -o a grader.cpp a.cpp -O2 -std=c++14 -Wall -fsanitize=undefined && ./a < soul.in

implementer.cpp: In function ‘int main()’:
implementer.cpp:60:14: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   60 |         fread(Interactor::rbuf,1,50000000,stdin);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:2:9: fatal error: soul.h: No such file or directory
    2 | #include"soul.h"
      |         ^~~~~~~~
compilation terminated.