#include<stdio.h>
#include<ctype.h>
#include<memory.h>
#include<set>
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();
		if(f) ret = -ret;
	}
	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 n, val[maxn];
ll C, f[maxn], g[maxn];
char s[maxn];
ll min(ll a, ll b) {return a > b? b: a;}
int main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	int T;
	read(T);
	while(T--)
	{
		read(n, C);
		for(int i = 0; i <= n + 1; i++) f[i] = g[i] = 0x3f3f3f3f3f3f3f3f;
		char ch = gtchar();
		while(!isalpha(ch)) ch = gtchar();
		for(int i = 1; i <= n; i++) s[i] = ch, ch = gtchar();
		int cnt = 0;
		for(int i = 1, j = n; i < j; i++, j--) if(s[i] != s[j]) ++cnt;
		if(!cnt)
		{
			for(int i = 1; i <= n; i++) printf("0 ");
			return puts(""), 0;
		}
		int mid = n / 2, cc = 0;
		ll sum = 0;
		std::set<int> pos;
		for(int i = 1; i <= n; i++)
		{
			read(val[i]);
			if(s[i] != s[n - i + 1])
			{
				if(i <= mid) sum += val[i], ++cc, pos.insert(i);
				else if(val[i] < val[n - i + 1]) sum += val[i] - val[n - i + 1], pos.erase(n - i + 1), pos.insert(i);
			}
			if(cc == cnt) f[i] = sum + (i - *pos.begin()) * C;
		}
		pos.clear();
		sum = cc = 0;
		for(int i = n; i; i--)
		{
			if(s[i] != s[n - i + 1])
			{
				if(i > mid) sum += val[i], ++cc, pos.insert(i);
				else if(val[i] < val[n - i + 1]) sum += val[i] - val[n - i + 1], pos.erase(n - i + 1), pos.insert(i);
			}
			if(cc == cnt) g[i] = sum + (*pos.rbegin() - i) * C;
		}
		for(int i = 1; i <= n; i++) f[i] = min(f[i], f[i - 1] + C);
		for(int i = n; i; i--) g[i] = min(g[i], g[i + 1] + C);
		ll mn = 0x3f3f3f3f3f3f3f3f;
		for(int i = 1; i <= n; i++) f[i] = min(f[i], mn + i * C), mn = min(mn, g[i] - i * C);
		mn = 0x3f3f3f3f3f3f3f3f;
		for(int i = n; i; i--) g[i] = min(g[i], mn - i * C), mn = min(mn, f[i] + i * C);
		for(int i = 1; i <= n; i++) printf("%lld ", min(f[i], g[i]));
		puts("");
	}
	return 0;
}