#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define int long long
#define fire signed
#define il inline
template<class T> il void print(T x) {
	if(x<0) printf("-"),x=-x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
template<class T> il void in(T &x) {
    x = 0; char ch = getchar();
    int f = 1;
    while (ch < '0' || ch > '9') {if(ch=='-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    x *= f;
}
int T=1;
const int N=5e6+10;
int n,c,cnt;
int h[N],f[N][4],sum[N];
string a; 
il void solve1() {
	rep(i,1,n) {
		sum[i]=sum[i-1];
		if(a[i]!=a[n-i+1]) {
			sum[i]++;
		}
	}
	int lst=false,ss=0,pr=0;
	rep1(i,n,(n+1)/2+1) {
		if(a[i]!=a[n-i+1]) {
			if(!lst) pr=i;
			lst=i;
			ss+=h[i];
		}
	}
	f[lst][1]=ss+(pr-lst)*c;
	int now=0;
	rep1(i,lst-1,1) {
		if(sum[i-1]==0) {
			now=i;
			break;
		}
		if(a[i]==a[n-i+1]) f[i][1]=f[i+1][1]+c;
		else {
			if(i<=(n+1)/2&&h[i]<h[n-i+1]) f[i][1]=min(f[i][1],f[i+1][1]-max(h[i],h[n-i+1])+min(h[i],h[n-i+1])+c);
			else f[i][1]=min(f[i][1],f[i+1][1]+c);
		}
	}
	int j=now,s=0,cc=0;
	while(j<=n) {
		int dui=n-j+1;
		if(a[j]!=a[dui]) {
			if(dui>=now&&dui<=j) {
				if(h[j]<h[dui]) {
					s-=h[dui];
					s+=h[j];
				}
			}else s+=h[j],cc++;
		}
		if(cc==cnt) f[now][1]=min(f[now][1],s+(j-now)*c);
		j++;
	}
	rep1(i,now-1,1) f[i][1]=min(f[i][1],f[i+1][1]+c);
}
il void solve2() {
	int lst=false;
	int ss=false,pr=0;
	rep(i,1,(n+1)/2) {
		if(a[i]!=a[n-i+1]) {
			if(!lst) pr=i;
			lst=i;
			ss+=h[i];
		}
	}
	f[lst][0]=ss+(lst-pr)*c;
	int now=0;
	rep(i,lst+1,n) {
		if(sum[n]-sum[i]==0) {
			now=i;
			break;
		}
		if(a[i]==a[n-i+1]){
			f[i][0]=f[i-1][0]+c;
		} else {
			if(h[i]<h[n-i+1]) f[i][0]=min(f[i][0],f[i-1][0]-h[n-i+1]+h[i]+c);
			else f[i][0]=min(f[i][0],f[i-1][0]+c);
		}
	}
	int j=now,s=0,cc=0;
	while(j>=1) {
		int dui=n-j+1;
		if(a[j]!=a[dui]) {
			if(dui>=j&&dui<=now) {
				if(h[j]<h[dui]) {
					s-=h[dui];
					s+=h[j];
				}
			}else s+=h[j],cc++;
		}
		if(cc==cnt) f[now][0]=min(f[now][0],s+(now-j)*c);
		j--;
	}
	rep(i,now+1,n) f[i][0]=min(f[i][0],f[i-1][0]+c);
}
il void solve() {
	in(n),in(c);
	cin>>a;
	a=" "+a;
	rep(i,1,n) in(h[i]);
//	if(n==1) {
//		cout<<0<<endl;
//		return ;
//	}
	cnt=false;
	rep(i,1,n) if(a[i]!=a[n-i+1]) cnt++;
	rep(i,0,n+1) rep(j,0,3) f[i][j]=2e18;
	cnt/=2;
//	if(cnt==0) {
//		cout<<0<<endl;
//		return ;
//	}
	solve1();
	solve2();
	rep(i,1,n) f[i][3]=f[i][0],f[i][2]=f[i][1];
	rep1(i,n,1) f[i][3]=min(f[i][3],f[i+1][3]+c);
	rep(i,1,n) f[i][2]=min(f[i][2],f[i-1][2]+c),printf("%lld ",min(f[i][2],f[i][3]));
	puts("");
}
fire main() {
//	freopen(".in","r",stdin);
//	freopen("s.out","w",stdout);
	in(T);
	while(T--) {
		solve();
	}
	return false;
}