#include<stdio.h>
#include<ctype.h>
#include<algorithm>
namespace IO {
	constexpr int bufsize = 230005;
	char buf[bufsize], *f1, *f2;
	char gtchar() {return f1 == f2 && (f2 = buf + fread(f1 = buf, 1, bufsize, stdin)) == buf? EOF: *f1++;}
	template<typename T> void read(T &ret)
	{
		int f = ret = 0;
		char ch = gtchar();
		while(!isdigit(ch)) f = ch == '-', ch = gtchar();
		while(isdigit(ch)) ret = (ret << 3) + (ret << 1) + (ch ^ 48), ch = gtchar();
	}
	template<typename T, typename ...t> void read(T &a, t &...b) {read(a), read(b...);}
}using IO::read, IO::gtchar;
typedef long long ll;
constexpr int maxn = 1000005;
int T, n, mid, h[maxn], nxt[maxn];
ll C, mn, sum[maxn], s[maxn], val[maxn];
char str[maxn];
void chmin(int &a, int b) {if(a > b) a = b;}
void chmin(ll &a, ll b) {if(a > b) a = b;}
int min(int a, int b) {return a > b? b: a;}
void solve()
{
	for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (str[i] == str[n - i + 1]? 0: h[i]);
	for(int i = 1; i <= mid; i++) s[i] = s[i - 1] + (str[i] == str[n - i + 1]? 0: min(h[i], h[n - i + 1]));
	int fir = nxt[1], lst = n - fir + 1;
	mn = 1e15;//x->fir->y(x<=mid)
	for(int i = lst; i >= n - i + 1; i--) chmin(mn, C * i - s[n - i] + sum[n - i]);
	for(int i = fir; i <= n - i + 1; i++) chmin(val[i], C * (i - 2 * fir) + s[mid] + mn);//, printf("update %d:%lld\n", i, C * (i - 2 * fir) + s[mid] + mn);
//	puts("===");
	mn = 1e15;//x->y->fir(x>mid)
	for(int i = lst; i >= n - i + 1; i--)
	{
		chmin(mn, 2 * C * i + sum[n - i] - s[n - i]);
		chmin(val[i], s[mid] - C * (i + fir) + mn);//, printf("update %d:%lld\n", i, s[mid] - C * (i + fir) + mn);
	}
//	puts("===");//x<=mid
	for(int i = mid; i >= fir; i--) chmin(val[i], s[mid] - C * (i + fir) + mn);//, printf("update %d:%lld\n", i, s[mid] - C * (i + fir) + mn);
//	puts("===");//x->fir->mid(x<=mid)
	int tmp = n - nxt[n - mid + 1] + 1;
	for(int i = fir; i <= n - i + 1; i++) chmin(val[i], sum[mid] + C * (tmp - fir) + C * min(i - fir, i < tmp? tmp - i: (i - tmp)));//, printf("update %d:%lld\n", i, sum[mid] + C * (mid - fir) + C * min(i - fir, i < mid? mid - i: (i - mid)));
//	puts("===");
	mn = 1e15;//x->y(x<fir<mid<=y)
	for(int i = lst; i >= n - i + 1; i--) chmin(mn, sum[n - i] - s[n - i] + C * i);
	for(int i = 1; i < fir; i++) chmin(val[i], s[mid] - C * i + mn);//, printf("update %d:%lld\n", i, s[mid] - C * i + mn);
	for(int i = 1; i < fir; i++) chmin(val[i], sum[mid] + C * (tmp - i));//, printf("update %d:%lld\n", i, sum[mid] + C * (tmp - i));
//	puts("\n");
}
int main()
{
	read(T);
	while(T--)
	{
		read(n, C), mid = n >> 1, nxt[n + 1] = 0;
		for(int i = 1; i <= n; i++) val[i] = 1e15;
		char ch = gtchar();
		while(!isalpha(ch)) ch = gtchar();
		for(int i = 1; i <= n; i++) str[i] = ch, ch = gtchar();
		for(int i = n; i; i--) nxt[i] = str[i] == str[n - i + 1]? nxt[i + 1]: i;
		for(int i = 1; i <= n; i++) read(h[i]);
		if(!nxt[1])
		{
			puts("0");
			continue;
		}
		solve();
//		for(int i = 1; i <= n; i++) printf("%lld ", val[i]);
//		puts("");
		std::reverse(h + 1, h + 1 + n), std::reverse(val + 1, val + 1 + n);
		solve();
		std::reverse(val + 1, val + 1 + n);
		for(int i = 1; i <= n; i++) printf("%lld ", val[i]);
		puts("");
	}
	return 0;
}