#include"path.h"
#include<bits/stdc++.h>
#include<algorithm>
int ask(int x,int y,int z);
int centroid(int id,int N,int M);

int jh[5];
int st[1000009];
bool cmp(int a,int b){
	int x=ask(a,b,st[1]);
	return x==a;
}
int centroid(int id,int N,int M){
	if(N==3)return ask(1,2,3);
	int cnt=0;
	for(int i=1;i<=N;++i){
		jh[++cnt]=i;
		int jb;
		if(cnt==3){
			jb=ask(jh[1],jh[2],jh[3]);
			for(int i=1;i<=2;++i){
				if(jh[i]==jb){
					int jb;
					jb=jh[3];
					jh[3]=jh[i];
					jh[i]=jb;
					continue;
				}
			}
			--cnt;
		}
		st[i]=i;
	}
	int jb;
	jb=st[1];
	st[1]=st[jh[1]];
	st[jh[1]]=jb;
	nth_element(st+2,st+2+N/2,st+2+N-1,cmp);
	return st[N/2+1];
}

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: In function ‘int centroid(int, int, int)’:
answer.code:38:9: error: ‘nth_element’ was not declared in this scope; did you mean ‘std::nth_element’?
   38 |         nth_element(st+2,st+2+N/2,st+2+N-1,cmp);
      |         ^~~~~~~~~~~
      |         std::nth_element
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:2:
/usr/include/c++/13/bits/stl_algo.h:4813:5: note: ‘std::nth_element’ declared here
 4813 |     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
      |     ^~~~~~~~~~~