现有的题解怎么全都是注意力惊人选手，畏惧了。

这里的式子是手推的，其中用到了神秘的待定系数法。

首先 $n$ 为偶数是简单的。

$n$ 为偶数时，所有数的出现次数都需要是偶数次，否则直接输出 No。

输出答案是简单的，直接构造一个回文就好。

随后考虑 $n$ 是奇数的情况。

我们肯定需要一个数放在中间。

出现次数为偶数的直接在两边回文消掉就好了。

但是我们显然不能够留下多个 $1$ 次的，否则一定无法保证其平均数。

因此，我们考虑将所有奇数消除到只剩下 $1$ 次或 $3$ 次。

特殊的，若初始没有出现次数为 $1$ 的：

• 将一个出现次数为奇数的放一个到中间，别的在两侧直接构造回文处理掉。

• 若没有奇数次的，把一个奇数拆成偶数 $+1$ 或者将一个偶数拆成奇数 $+1$。显然，奇数 $+1$ 还是 $-1$，奇偶性并不会变，所以都可以，而原本有奇数个奇数，所以拆奇数肯定没问题。

• 若仍然没有，说明只有一堆出现次数为 $2$ 的偶数，直接无解。

那么我们现在只剩下了一个子问题：将若干个出现次数为 $3$ 的放上去。

别的题解很多直接注意到了，因为我的注意力不是很惊人，我是用待定系数和暴力推的。

我们先写一个暴力，给我们搞一些例子：

• 1 1 2 3 2 2 1。

• 2 3 1 4 4 3 5 1 2 1 2 4 3。

尝试通过这个猜式子。

先猜参数。

首先，因为两侧的数量不一样，所以我们将颜色分成两部分。

第一部分是左边 $1$ 个，右边 $2$ 个。

第二部分是左边 $2$ 个，右边 $1$ 个。

两种摆法几乎完全不一样，猜测位置与下列两个参数有关：

• 出现了三次的数的数量。

• 当前是第几个数。

设中心点为 $mid$。

我们将这些数收集在一个数组中，设这个数组的大小为 $t$。

于是我们假设这三个点都是 $mid+a \times i+b \times t$ 的形式。

因为只有两个未知数，通过上面的例子，完全可以解出对应数值。

此处直接给出最后的结果了：

• 对于第一部分，三个点的下标为：$mid+i,mid+i+\frac t 2,mid - 2 \times i-\frac t 2$。

• 对于第二部分，三个点的下标为：$mid-i+\frac t 2,mid+4 \times \frac t 2-i+1,mid-5 \times \frac t 2+2 \times i-1$。

照着去实现就好。

:::success[代码]

//belong=构造(6g0ntkq0)
#include<bits/stdc++.h>
using namespace std;

const int N=2e5+5;
int col[N],ans[N],tmpx[N];

inline int read(){
	int s=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*f;
}

int main(){
    int T;cin>>T;
    while(T--){
        int n=read(),k=read();
        for(int i=1;i<=n;i++) col[read()]++;
        if(n%2==0){//偶数次，需要所有数出现次数都为偶数
            bool tag=1;
            for(int i=1;i<=k;i++)
                if(col[i]&1) tag=0;
            if(tag){
                int l=1,r=n;
                for(int i=1;i<=k;i++)
                    while(col[i]) ans[l]=ans[r]=i,l++,r--,col[i]-=2;
                puts("YES");
                for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
                cout<<"\n";
            }else puts("NO");
        }else{//奇数次，分类讨论
            int cnt=0;
            for(int i=1;i<=k;i++)
                if(col[i]==1) cnt++;
            if(cnt>1) puts("NO");//有不止一个出现次数为 1 的
            else if(cnt==0){
                int cntx=0;
                for(int i=1;i<=k;i++)
                    if(col[i]&1) cntx++;
                if(cntx%2==0) puts("NO");//出现次数为奇数的是偶数个，删掉一个后也一定无法处理
                else{//把一个奇数拆成偶数+1 || 将一个偶数拆成奇数+1
                    //显然，奇数 +1 / -1，奇偶性并不会变，所以都可以，而原本有奇数个奇数，所以拆奇数肯定没问题
                    int l=1,r=n;//l 和 r 记录当前填写的位置
                    for(int i=1;i<=k;i++)
                        if(col[i]&1){ans[n/2+1]=i;col[i]--;break;}
                    int idx=0;//记录有多少个 3 个的
                    //先拆掉偶数，压缩奇数数量
                    for(int i=1;i<=k;i++){
                        if(col[i]%2==0){//为偶数，全部用掉
                            while(col[i]) ans[l]=ans[r]=i,l++,r--,col[i]-=2;
                        }else{//为奇数，使用到只剩 3 个
                            while(col[i]>3) ans[l]=ans[r]=i,l++,r--,col[i]-=2;
                            tmpx[++idx]=i;
                        }
                    }
                    //处理当前出现次数为 3 的
                    int mid=n/2+1,t=idx/2;
                    for(int i=1;i<=t;i++) ans[mid+i]=ans[mid+i+t]=ans[mid-2*i-t]=tmpx[i];
                    for(int i=t+1;i<=idx;i++) ans[mid-i+t]=ans[mid-i+4*t+1]=ans[mid-5*t+2*i-1]=tmpx[i];  
                    //输出答案
                    puts("YES");
                    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
                    puts("");
                } 
            }else{//恰好一个，可以处理
                int cntx=0;
                for(int i=1;i<=k;i++)
                    if(col[i]!=1 && col[i]&1) cntx++;
                if(cntx&1) puts("NO");//有奇数个出现次数为奇数的，无法处理
                else{
                    int l=1,r=n;//mid 记录中间的值，l 和 r 记录当前填写的位置
                    for(int i=1;i<=k;i++)
                        if(col[i]==1){ans[n/2+1]=i;col[i]--;break;}//把中间的数放了
                    int idx=0;//记录有多少个 3 个的
                    //先拆掉偶数，压缩奇数数量
                    for(int i=1;i<=k;i++){
                        if(col[i]%2==0){//为偶数，全部用掉
                            while(col[i]) ans[l]=ans[r]=i,l++,r--,col[i]-=2;
                        }else{//为奇数，使用到只剩 3 个
                            while(col[i]>3) ans[l]=ans[r]=i,l++,r--,col[i]-=2;
                            tmpx[++idx]=i;
                        }
                    }
                    //处理当前出现次数为 3 的
                    int mid=n/2+1,t=idx/2;
                    for(int i=1;i<=t;i++) ans[mid+i]=ans[mid+i+t]=ans[mid-2*i-t]=tmpx[i];
                    for(int i=t+1;i<=idx;i++) ans[mid-i+t]=ans[mid-i+4*t+1]=ans[mid-5*t+2*i-1]=tmpx[i]; 
                    //输出答案
                    puts("YES");
                    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
                    puts("");
                }
            }
        }
        //多测记得清空
        for(int i=1;i<=k;i++) col[i]=0;
    }
	return 0;
}

:::