#include<bits/stdc++.h>
#include "path.h"
using namespace std;
#define ll int
const ll N=1e5+10;
ll n,m;ll ti;
ll ttt;inline bool cmp(ll x,ll y){return ask(x,y,ttt)==x;}
ll vis[N];ll tim=0; 
inline bool pd(ll pos,ll sx,ll sy,ll x,ll y,vector<ll>&hs){
    ll nw=0,cnt=0;if(sx>sy)nw=x,cnt=sx;if(sy>sx)nw=y,cnt=sy;
    for(auto o:hs){
        if(vis[o]!=tim)continue;
        if(!nw||ask(pos,o,nw)!=pos)nw=o,cnt++;
        else{cnt--;if(!cnt)nw=0;}
    }if(nw==x||nw==y||!nw)return true;
    cnt=0;for(auto o:hs)if(vis[o]==tim)cnt+=ask(o,nw,pos)!=pos;
    return cnt*2<=n;
}
ll p[N];
mt19937 rnd(114514);
ll centroid(ll id,ll NN,ll MM){
    n=NN;m=MM;if(n==3)return ask(1,2,3);
    if(id==3||id==5){
        ll x=1,y=2;for(int i=3;i<=n;i++){
            ll tem=ask(x,y,i);if(tem==x)x=i;if(tem==y)y=i;
        }ttt=x;for(int i=1;i<=n;i++)p[i]=i;
        nth_element(p+1,p+(n+1)/2,p+n+1,cmp);return p[(n+1)/2];
    }vector<ll>nw,f,hs;ll tot=0;while(1){
        ll x=rnd()%n+1,y=rnd()%n+1;while(x==y)x=rnd()%n+1,y=rnd()%n+1;//tot++;cout<<tot<<'\n';
        nw.clear();f.clear();hs.clear();for(int i=1;i<=n;i++)f.emplace_back(i);
        ll sx=1,sy=1;while(x!=y&&!f.empty()){
            for(auto o:f){
                if(o==x||o==y)continue;ll tem=ask(o,x,y);
                if(tem==x)sx++;else if(tem==y)sy++;
                else if(tem==o)hs.emplace_back(o),nw.emplace_back(o);else nw.emplace_back(o);
            }if(sx*2>n||sy*2>n)break;
            ll g=nw[rnd()%nw.size()];ll pos=0;for(int i=0;i<hs.size();i++){if(!pos)pos=hs[i];else pos=ask(pos,hs[i],g);}
            ll tx=sx,ty=sy;tim++;if(pos==112){
                cout<<1;
            }for(auto o:nw){
                if(o==pos)continue;
                if(ask(o,pos,x)!=pos)tx++;
                else if(ask(o,pos,y)!=pos)ty++;
                else vis[o]=tim;
            }if(tx*2<=n&&ty*2<=n&&pd(pos,tx,ty,x,y,nw))return pos;
            if(tx>ty)y=pos,sy++;else x=pos,sx++;swap(nw,f);nw.clear();
        }
    }
}