#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define mkp make_pair
#define pb push_back
#define fir first
#define pp pop_back
#define eps 1e-8
#define sec second
#define pii pair<int,int>
#define eb emplace_back
#define file(filename) freopen(filename".in","r",stdin);freopen(filename".out","w",stdout);
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Dor(i,a,b) for(int i=a;i>=b;i--)
//==============================================================================================
// Fast IO

template<typename T>
inline T read(){
	T f=1,c=0;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(isdigit(ch)){
		c=(c<<1)+(c<<3)+(ch^48);
		ch=getchar();
	}
	T a=f*c;
	return a;
}

//=============================================================================================
//code here
char ch[1000010];
ll a1[1000010],a2[1000010];
int n,c,h[1000010];
void add(int x,ll  w){
	a1[x]=min(a1[x],w);
	a2[x]=min(a2[x],w);
}
void solve(){
	int i,j;scanf("%d%d",&n,&c);scanf("%s",ch+1);
	for(i=1;i<=n;i++) scanf("%d",&h[i]);
	int l=1,r=n;while(l<r&&ch[l]==ch[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(ch[p]==ch[n-p+1]) p--;//cerr<<l<<' '<<r<<'\n';
	ll Sum=0;
	for(i=l;i<=r;i++){
		if(ch[i]!=ch[n-i+1]) {
			if(i<=n/2) Sum+=h[i];
			else Sum+=min(h[i],h[n-i+1])-h[n-i+1];
		}
		if(i>=p) add(l,Sum+1ll*(i-l)*c);add(i,Sum+1ll*(i-l)*c);;
	}
	p=n-p+1;Sum=0;
	for(i=r;i>=l;i--){
		if(ch[i]!=ch[n-i+1]) {
			if(i>n/2) Sum+=h[i];
			else Sum+=min(h[i],h[n-i+1])-h[n-i+1];
		}
		if(i<=p) add(i,Sum+1ll*(r-i)*c);add(r,Sum+1ll*(i-l)*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("%lld%c",min(a1[i],a2[i])," \n"[i==n]);

}
signed main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}
//吾日三省吾身
//输入多而不read()乎？
//1e18而不开longlong乎？
//多测不清乎？