奶龙。

不可爱**卡常随机化奶氏恶心交互。

给出两个做法，一个是我自己写的，一个是根据 @Monomial 的口胡改的。

做法 1

第一种做法感觉比较显然，先考虑链的做法：

若长度大于 $3$（小于 $3$ 不用做，$3$ 做一次）选定两个点，如果选择得当，点集会被分为 $A,B$ 两部分（忽略 $mid$）。

选择得当的条件是 $a,b$ 距离大于到两边距离。

感性理解一下，这个大约需要 $1$ 到 $2$ 次随机 $a,b$。

由于随机，序列被较为平均的分为 $2$ 部分，认为递归次数为 $\mathcal{O}(n\log n)$ 的。

现在考虑环上，圆上任选一条弦，若弦长不小于 $\left \lfloor \frac{n}{3}\right \rfloor$，则圆上其他点被（由弦的垂直平分线）均分（先忽略 $mid$），期望次数 $1.5$ 次。

交上去发现 $97\text{pts}$，十分火大。

优化：

首先记忆化所有询问，用哈希或者 map 实现。

玄学优化随机方式，这里有三种：

1. 直接随机数，这个貌似是最劣的。

2. $\operatorname{shuffle}$ 后遍历整个序列和 $a_l$ 取弦。

3. 启发式的第二种，在检查的时候选择任意的距离更远点。

经过尝试，第二种或者第三种都可以通过。

分治后要拼在一起，设 $A=a[l\dots div],B=a[div+1\dots r]$，通过最多两次询问拼接：

1. 询问 $(l,div,div+1)$，未出现 $div+1$ 则反序 $B$ 后再次询问 $(l,div,div+1)$，若 $l$ 出现则反序 $A$。

2. 若 $B$ 未被反序，则询问 $(div,div+1,r)$，出现 $r$ 则反序 $B$。

环的拼接通过一次询问特判即可。

可能负优化：

对于有中点的区间，取出中点放到 $A,B$ 两边，可以省去合并的询问。

拼上之后用 random_device 多交几次可以通过。

做法 2

@Monomial 想了一个倍增做法说假了。

所以我根据这一提示词（反向）胡了一个确定性做法：

首先对于一个点我们可以最多 $2n$ 次（期望 $n$ 次）找到任意一个相邻点，每次找另一个点然后找离 $x$ 近的，迭代 $\log n$ 次，每次长度至少减半。

对于一个序列，若我们知道了两个端点，可以 $\mathcal{O}(n)$ 得出中点（如果有）以及两边的点分类。

这样就好了，随便从环上找一个点断开，得到对面的中点，如果长度为偶数没有中点，找一个点垫一下长度减一就得到了中点，以中点开始向两边分治即可。

复杂度同上，虽然不依赖随机化，但是期望次数巨大（感觉常数是 $3$，做法 1 大约 $2$ 左右），所以我没有实现本算法。

做法 1 的代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
mt19937 Rnd(1e9+7);
random_device rnd;
#define vi vector<int>
vi d1,d2;
int n,a[N];

vector<pair<int,int>>mps[N];
map<int,int>vis;
int tot=0;
vector<pair<int,int> >temp;
int Hash(int x,int y,int z){
	int tmp[3]={x,y,z};
	sort(tmp,tmp+3);
	return tmp[0]*n*n+tmp[1]*n+tmp[2];
}
vector<pair<int,int>> Query(int x,int y,int z){
	int hs=Hash(x,y,z);
	if(vis[hs])return mps[vis[hs]];
	vis[hs]=++tot;mps[tot].clear();
	printf("? %d %d %d\n",x-1,y-1,z-1),fflush(stdout);
	int Round;scanf("%d",&Round);
	while(Round--){
		int ax,ay;scanf("%d%d",&ax,&ay);
		mps[tot].emplace_back(make_pair(ax+1,ay+1));
	}
	return mps[vis[hs]];
}
//所有询问记忆化。
void Hahahaha(int l){
	int cpr[3]={0,0,0};
	temp=Query(a[l],a[l+1],a[l+2]);
	for(auto [ax,ay]:temp){
		for(int x=0;x<3;x++)
			if(ax==a[l+x]||ay==a[l+x])cpr[x]++;
	}
	if(cpr[0]>=2)swap(a[l],a[l+1]);
	if(cpr[2]>=2)swap(a[l+1],a[l+2]);
}
map<pair<int,int> ,int>fw;//fw 边
int Mid=0,Xmd=0;
bool WhatCanISay(int L,int R,int x,int &y){
	d1.clear(),d2.clear(),d1.emplace_back(x),d2.emplace_back(y);
	Mid=0;
	for(int z,p=L;p<=R;p++){
		z=a[p];if(z==x||z==y)continue;
		int fl=0;
		temp=Query(x,y,z);
		bool fl1=0,fl2=0;
		for(auto [ax,ay]:temp){
			fw[make_pair(ax,ay)]=fw[make_pair(ay,ax)]=1;
			if(ay==z)swap(ax,ay);
			if(ax!=z)continue;
			fl=(ay==x?1:2);
			if(ay==x)fl1=1;
			if(ay==y)fl2=1;
		}
		if(fl1&&fl2){
			Mid=z,Xmd=fl=d1.size()<d2.size()?1:2;
		}
		if(!fl){
			y=z;
			return 0;
		}
		((fl==1)?(d1.emplace_back(z)):(d2.emplace_back(z)));
	}
	return 1;
}
//void Kobe(int l,int r,int &x,int &y){
//	y=x=rnd()%(r-l+1)+l;
//	while(y==x)y=rnd()%(r-l+1)+l;
//}
void Man(int l,int r){
	int len=r-l+1;
	if(len<3)return;
	if(len==3){Hahahaha(l);return;}
	shuffle(a+l,a+r+1,rnd);
	fw.clear();
	{
		//while(1){
		//	int xx,yy;Kobe(l,r,xx,yy);
		//	xx=a[xx],yy=a[yy];
		//	if(fw[make_pair(xx,yy)])continue;
		//	Mid=0;
		//	if(WhatCanISay(l,r,xx,yy))break;
		//}
		
		//for(int i=l+1;i<=r;i++){
		//	if(fw[make_pair(a[l],a[i])])continue;
		//	if(WhatCanISay(l,r,a[l],a[i]))break;
		//}

		int yy=a[r];
		while(!WhatCanISay(l,r,a[l],yy));
	}
	int nw=l-1,dv=0;
	for(auto x:d1)a[++nw]=x;
	dv=nw;
	for(auto x:d2)a[++nw]=x;
	int md=0,xd=Xmd;
	if(!md){
		Man(l,dv),Man(dv+1,r);
		if(len!=n){
			bool fl1=0,fl2=0;
			if(l!=dv){
				bool fl3=0;
				temp=Query(a[l],a[dv],a[dv+1]);
				for(auto [ax,ay]:temp){
					if(ax!=a[dv+1]&&ay!=a[dv+1])continue;
					fl3=1;
					if(ax==a[dv+1])swap(ax,ay);
					if(ax==a[l])fl1=1;
				}
				if(!fl3)fl2=1;
				if(!fl1){
					temp=Query(a[l],a[dv],a[r]);
					for(auto [ax,ay]:temp){
						if(ax!=a[r]&&ay!=a[r])continue;
						if(ax==a[r])swap(ax,ay);
						if(ax==a[l])fl1=1;
					}
				}
			}
			if(fl1)reverse(a+l,a+dv+1);
			if(dv+1!=r&&!fl2){
				temp=Query(a[dv],a[dv+1],a[r]);
				for(auto [ax,ay]:temp){
					if(ax!=a[dv]&&ay!=a[dv])continue;
					if(ax==a[dv])swap(ax,ay);
					if(ax==a[r])fl2=1;
				}
				temp=Query(a[dv],a[dv+1],a[r]);
			}
			if(fl2)reverse(a+dv+1,a+r+1);
		}else{
			if(l==dv||r==dv+1)return;
			bool fl=0;
			temp=Query(a[l],a[r],a[dv]);
			for(auto [ax,ay]:temp){
				if(ax==a[r]||ay==a[r]){
					if(ax==a[r])swap(ax,ay);
					if(ax!=a[l])fl=1;
				}
			}
			if(fl)reverse(a+l,a+dv+1);
		}
	}else{
		if(xd==1){
			Man(l,dv);
			if(a[dv]!=md)reverse(a+l,a+dv+1);
			Man(dv,r);
			if(a[dv]!=md)reverse(a+dv,a+r+1);
		}else{
			++dv;
			Man(dv,r);
			if(a[dv]!=md)reverse(a+dv,a+r+1);
			Man(l,dv);
			if(a[dv]!=md)reverse(a+l,a+dv+1);
		}
	}
}
void ManbaOut(){
	printf("!"),fflush(stdout);
	for(int i=1;i<=n;i++)printf(" %d",a[i]-1);
	printf("\n"),fflush(stdout);
}
void work(){
	tot=0;vis.clear();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)a[i]=i;
	Man(1,n);
	ManbaOut();
}
int main(){
	int T,LIM;
	scanf("%d%d",&T,&LIM);
	while(T--)work();
	return 0;
}
//近似 nlog n 次数的询问。
//考虑这样计算：
//给出的答案相当于圆上三点走最小弧哪两点距离最小。
//考虑一个弱化版：
/*
对于链上，给定 3 个点，每次询问一组点：
得到：
|  A  X  B  |(mid)|  C  Y  D  |
其中在这组询问中 (A,B) 相同，(C,D) 相同，mid 可以随机归 A B 还是 C D。
但是对于大体上是值域减半，
值域下降到 3 以下后采用暴力询问，期望询问次数为 nlogn 级别。
*/
//本题：
/*
环的问题可以视为特殊的链，任意一组 x y 都可以直接把圆拆成两半。
但是要得到具体的确定距离 x 还是 y 近需要令 x y 距离 >1/3 n
*/