#include "path.h"
#include<bits/stdc++.h>
using namespace std; 
const int N=3.1e5;
int a[N];
int p[N],tp,q[N],tq;
bool flg[N];
int centroid(int idd,int n,int m){
	for(int i=1;i<=n;++i)
		flg[i]=0;
	srand(time(0));
//	cerr<<idd<<" "<<n<<" "<<m<<endl;
	if(idd==1){
		return ask(1,2,3);
	}
	if(idd==3){
		int l=rand()%n+1,r=rand()%n+1;
		for(int i=1;i<=n;++i)
			a[i]=i;
		random_shuffle(a+1,a+n+1);
		for(int i=1;i<=n;++i){
			if(a[i]==l||a[i]==r) continue;
			int x=ask(l,a[i],r);
			if(x==l)
				l=a[i];
			else if(x==r)
				r=a[i];
		}
//		cerr<<l<<" "<<r<<endl;
		random_shuffle(a+1,a+n+1);
		for(int i=1,x,cntx=0,cnty=0;i<=n;++i){
			x=a[i];
			if(flg[x]) continue;
			tp=tq=0;
			for(int j=1;j<=n;++j){
				if(j==x||flg[j]) continue;
				if(ask(l,x,j)==j)
					p[++tp]=j;
				else
					q[++tq]=j;
			}
//			cerr<<x<<" "<<tp+cntx<<" "<<tq+cnty<<endl;
			if(tp+cntx==tq+cnty){
				return x;
			}
			if(tp+cntx<tq+cnty){
				for(int k=1;k<=tp;++k){
					flg[p[k]]=1;
//					cerr<<"change"<<p[k]<<endl;
					++cntx;
				}
				tp=tq=0;
			}
			else{
				for(int k=1;k<=tq;++k){
					flg[q[k]]=1;
//					cerr<<"change"<<q[k]<<endl;
					++cnty;
				}
				tp=tq=0;
			}
		}
	}
}