#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int nd[N],V[N];
long long val[N];
char s[N];
int main()
{
	int T;cin>>T;
	while(T--)
	{
		int n,C,pl=0,pr=0;
		cin>>n>>C>>s+1;
		for(int i=1;i<=n;++i)cin>>V[i];
		for(int i=1;i<=n;++i)nd[i]=s[i]!=s[n-i+1],val[i]=1e18;
		for(int i=1;i<=n;++i)if(nd[i])pr=i;
		if(!pr){for(int i=1;i<=n;++i)cout<<"0 ";cout<<"\n";continue;}
		pl=n-pr+1;
		{
			long long mn=0,t;int z=-1;
			for(int i=pr;i>n/2;--i)if(nd[i])mn+=V[i],z=i;
			assert(z!=-1);
			val[pr]=1ll*(pr-z)*C+mn;
			for(int i=z-1;i>pl;--i)
			{
				if(nd[i])mn-=V[n-i+1]-min(V[i],V[n-i+1]),
					val[pr]=min(val[pr],1ll*(pr-i)*C+mn);
				val[i]=1ll*(pr-i)*C+mn;
			}
		}
		{
			long long mn=0;int z=-1;
			for(int i=pl;i<=n/2;++i)if(nd[i])mn+=V[i],z=i;
			assert(z!=-1);
			val[pl]=1ll*(z-pl)*C+mn;
			for(int i=z+1;i<pr;++i)
			{
				if(nd[i])mn-=V[n-i+1]-min(V[i],V[n-i+1]),
					val[pr]=min(val[pr],1ll*(i-pl)*C+mn);
				val[i]=1ll*(i-pl)*C+mn;
			}
		}
//		for(int i=1;i<=n;++i)cout<<val[i]<<' ';cout<<"\n";
		for(int i=2;i<=n;++i)val[i]=min(val[i],val[i-1]+C);
		for(int i=n-1;i;--i)val[i]=min(val[i],val[i+1]+C);
		for(int i=1;i<=n;++i)cout<<val[i]<<' ';cout<<"\n";
	}
	return 0;
}