#include <iostream>
using namespace std;
#define int long long
const int maxn = 1e6+10;
int n,C,a[maxn],app[maxn],tot = 0,rr[maxn],ll[maxn]; char s[maxn];
void solve(int ans[]) {
	int ss = 0,tt = 0; tot = 0;
	for(int i = 1; i <= n+1-i; i++) {
		if(s[i] != s[n+1-i]) ss = (!ss)?i:ss,tt = i;
	}
	for(int i = 1; i <= n; i++) if(s[i] != s[n+1-i]) app[++tot] = i;
	if(!ss) {for(int i = 1; i <= n; i++) ans[i] = 0; return ;}
	int cum = 0;
	for(int i = ss; i <= tt; i++) if(s[i] != s[n+1-i]) cum += a[i];
	ans[ss] = cum + C*(tt-ss); //printf("%lld\n",ans[ss]);
	for(int i = (tot>>1)+1; i <= tot; i++) {
		int x = app[i];
		if(s[x] != s[n+1-x]) cum += min(a[x],a[n+1-x])-a[n+1-x];
		ans[ss] = min(ans[ss],cum+C*(x-ss));
		//printf("%lld %lld\n",cum,x);
	} //printf("%lld\n",ans[ss]);
	for(int i = ss-1; i >= 1; i--) ans[i] = ans[i+1]+C;
	for(int i = ss+1; i <= app[(tot>>1)+1]; i++) {
		if(s[i-1] != s[n+2-i]) cum += a[n+2-i]-min(a[i-1],a[n+2-i]);
		ans[i] = cum+C*(app[tot]-i);
	}
	//for(int i = 1; i <= n; i++) printf("%lld ",ans[i]); putchar('\n');
	for(int i = 2; i <= n; i++) {
		if(ans[i]) ans[i] = min(ans[i-1]+C,ans[i]);
		else ans[i] = ans[i-1]+C;
	}
	//for(int i = 1; i <= n; i++) printf("%lld ",ans[i]); putchar('\n');
}
signed main() {
	cin.tie(0)->sync_with_stdio(false);
	int T; cin >> T;
	while(T--) {
		tot = 0;
		cin >> n >> C >> (s+1); for(int i = 1; i <= n; i++) cin >> a[i];
		solve(rr); tot = 0;
		for(int i = 1; i <= n; i++) if(i<n+1-i) swap(a[i],a[n+1-i]); solve(ll);
		for(int i = 1; i <= n; i++) printf("%lld ",min(rr[i],ll[n+1-i]));
		putchar('\n');
		//for(int i = 1; i <= n; i++) app[i] = 0;
	}
	return 0;
}