#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=1e6+5,M=N*4,K=600+5,mod=998244353,Mod=mod-1;const db eps=1e-6;const ll INF=1e18+7;mt19937 rnd(263082);
int n,C,A[N];char s[N];
ll a1[N],a2[N];
void Add(int x,int y,ll w){
	a1[x]=min(a1[x],w);a2[x]=min(a2[x],w);
	a1[y]=min(a1[y],w);a2[y]=min(a2[y],w);
}
void Solve(){
	int i,j;scanf("%d%d",&n,&C);scanf("%s",s+1);
	for(i=1;i<=n;i++) scanf("%d",&A[i]);
	int l=1,r=n;while(l<r&&s[l]==s[r]) l++,r--;
	if(l>=r){for(i=1;i<=n;i++) printf("0 ");printf("\n");return;}
	fill(a1,a1+n+2,INF);fill(a2,a2+n+2,INF);
	int p=n/2;while(s[p]==s[n-p+1]) p--;//cerr<<l<<' '<<r<<'\n';
	ll Sum=0;
	for(i=l;i<=r;i++){
		if(s[i]!=s[n-i+1]) {
			if(i<=n/2) Sum+=A[i];
			else Sum+=min(A[i],A[n-i+1])-A[n-i+1];
		}
		if(i>=p) Add(l,i,Sum+1ll*(i-l)*C);
	}
	p=n-p+1;Sum=0;
	for(i=r;i>=l;i--){
		if(s[i]!=s[n-i+1]) {
			if(i>n/2) Sum+=A[i];
			else Sum+=min(A[i],A[n-i+1])-A[n-i+1];
		}
		if(i<=p) Add(i,r,Sum+1ll*(r-i)*C);
	}
	for(i=1;i<=n;i++) a1[i]=min(a1[i-1]+C,a1[i]);
	for(i=n;i;i--) a2[i]=min(a2[i+1]+C,a2[i]);
	for(i=1;i<=n;i++) printf("%d%c",min(a1[i],a2[i])," \n"[i==n]);
}
int main(){
	int t=1;
	scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}