#pragma GCC optimize("Ofast","inline")
#include"path.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50;

mt19937 rad(time(0));

int n,m,vis[N];
vector<int>s,g;

void clear()
{
	s.clear();g.clear();
}

int rd(int l,int r)
{
	return rad()%(r-l+1)+l;
}

int chk(int x)
{
	int now=0,cnt=0;
	for(int i=1;i<=n;i++)if(i!=x)
	{
		if(!cnt)
		{
			now=i,cnt=1;
			continue;
		}
		if(ask(x,i,now)==x)cnt--;
		else cnt++;
	}
	cnt=1;
	for(int i=1;i<=n;i++)if(i!=x&&i!=now)cnt+=ask(x,i,now)!=x;
	return cnt<=m?x:0;
}

int sol(int u,int v,int ls,int rs,int ff=1)
{
	if(s.empty()||max(ls,rs)>m)return 0;
    if(u==v)return chk(u);
	int pos=g[rd(0,g.size()-1)],fa=s[0],tt=0,cc=0;
    for(auto x:s)if(x==pos)tt=1;
    for(auto x:s)cc+=(x==u)+(x==v);
    if(!tt)
    {
        for(auto x:s)if(x!=fa&&ask(x,fa,pos)==x)fa=x;
        pos=fa;
    }
    int cl=ls,cr=rs,c=0;
    vector<int>L,R;
    if(pos==u)
    {
        for(auto x:g)if(x!=pos)
        {
            if(ask(u,v,x)!=u)R.push_back(x),cr++;
            else c++;
        }
    }
    else if(pos==v)
    {
        for(auto x:g)if(x!=pos)
        {
            if(ask(u,v,x)!=v)L.push_back(x),cl++;
            else c++;
        }
    }
    else for(auto x:g)if(x!=pos)
    {
        if(x==u){L.push_back(x);cl++;continue;}
        if(x==v){R.push_back(x);cr++;continue;}
        int w=ask(x,u,pos);
        if(w!=pos){L.push_back(x);cl++;continue;}
        w=ask(x,v,pos);
        if(w!=pos){R.push_back(x);cr++;continue;}
        ++c;
    }
    if(max(cl,cr)<=m)
    {
        if(c<=m&&pos!=u&&pos!=v)return pos;
        return chk(pos);
    }
    for(auto x:L)vis[x]=0;
    for(auto x:R)vis[x]=1;
    vector<int>tmp;int F=cl<cr;
    for(auto x:s)if(x!=pos&&vis[x]==F)tmp.push_back(x);
    swap(tmp,s);vector<int>().swap(tmp);
    if(s.empty())return 0;
    if(F)
    {
        swap(g,R);
        vector<int>().swap(L);
        vector<int>().swap(R);
        int now=s[0];
        for(auto x:s)
        {
            if(x==pos)cerr<<1;
            if(x!=now&&ask(x,now,pos)==x)now=x;
        }
        return sol(now,v,cl+c+1,rs);
    }
    else
    {
        swap(g,L);
        vector<int>().swap(L);
        vector<int>().swap(R);
        int now=s[0];
        for(auto x:s)
        {
            if(x!=now&&ask(x,now,pos)==x)now=x;
            if(x==pos)cerr<<1;
        }
        return sol(u,now,ls,cr+c+1);
    }
}

int solve(int u,int v)
{
	if(u==v)return 0;
	for(int i=1;i<=n;i++)if(i==u||i==v||ask(u,v,i)==i)s.push_back(i);
	for(int i=1;i<=n;i++)g.push_back(i);
	return sol(u,v,0,0,0);
}

int centroid(int id,int N,int M)
{
	if(id==1)return ask(1,2,3);
    if(id==5||id==3)
    {
        int x=1,y=2;
        for(int i=1;i<=n;i++)
        {
            int w=ask(x,y,i);
            if(w==x)x=i;
            if(w==y)y=i;
        }
        int d[N];
        for(int i=1;i<=n;++i)d[i]=i;
        nth_element(d+1,d+(n+1)/2,d+n+1,[&](int a,int b){return ask(x,a,b)==a;});
        return d[(n+1)/2];
    }
	n=N;m=n/2;int ans=0;
	while(!(ans=solve(rd(1,n),rd(1,n))))clear();
    clear();
	return ans;
}