#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
int k,b;
int calc(int x){return k*x+b;}
}tr[4000005];
void change(int k,int l,int r,int x,int y,node w)
{
if(x<=l&&r<=y)
{
int mid=(l+r)>>1;
if(w.calc(mid)<tr[k].calc(mid))swap(w,tr[k]);
if(l==r)return;
if(w.calc(l)<tr[k].calc(l))change(k<<1,l,mid,x,y,w);
if(w.calc(r)<tr[k].calc(r))change(k<<1|1,mid+1,r,x,y,w);
return;
}
int mid=(l+r)>>1;
if(x<=mid)change(k<<1,l,mid,x,y,w);
if(y>mid)change(k<<1|1,mid+1,r,x,y,w);
}
int query(int k,int l,int r,int x)
{
if(l==r)return tr[k].calc(x);
int mid=(l+r)>>1,res=tr[k].calc(x);
if(x<=mid)res=min(res,query(k<<1,l,mid,x));
else res=min(res,query(k<<1|1,mid+1,r,x));
return res;
}
int T,n,c,nxt[1000005],sum[1000005],sum1[1000005],a[1000005];char s[1000005];
signed main()
{
cin.tie(0)->sync_with_stdio(0);
cin>>T;
while(T--)
{
cin>>n>>c>>(s+1);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=n;i>=1;i--)
{
nxt[i]=nxt[i+1];
if(s[i]!=s[n-i+1])nxt[i]=i;
}
if(!nxt[1])
{
for(int i=1;i<=n;i++)cout<<0<<' ';
cout<<'\n';continue;
}
for(int i=1;i<=n;i++)sum1[i]=sum1[i-1]+(s[i]!=s[n-i+1])*a[i];
for(int i=1;i<=n/2;i++)sum[i]=sum[i-1]+(s[i]!=s[n-i+1])*min(a[i],a[n-i+1]);
for(int i=1;i<=4*n;i++)tr[i]={0,1e18};
int p=nxt[1];
for(int i=p;i<=n/2;i++)//<=i 都归到一边
{
int l=p,r=n-nxt[i+1]+1;
int w=sum[n/2]-sum[i]+sum1[i];
if(1<=l-1)change(1,1,n,1,l-1,{-c,r*c+w});
if(l<=(l+r)/2)change(1,1,n,l,(l+r)/2,{c,(r-2*l)*c+w});
if((l+r)/2+1<=r)change(1,1,n,(l+r)/2+1,r,{-c,(2*r-l)*c+w});
if(r+1<=n)change(1,1,n,r+1,n,{c,-l*c+w});
}
for(int i=n-p+1;i>(n+1)/2;i--)//>=i 都归到一边
{
int l=nxt[n-i+2],r=n-p+1;
int w=sum1[n]-sum1[i-1]+sum[n/2]-sum[n-i+1];
if(l)change(1,1,n,1,l-1,{-c,r*c+w});
if(l<=(l+r)/2)change(1,1,n,l,(l+r)/2,{c,(r-2*l)*c+w});
if((l+r)/2+1<=r)change(1,1,n,(l+r)/2+1,r,{-c,(2*r-l)*c+w});
if(r+1<=n)change(1,1,n,r+1,n,{c,-l*c+w});
}
for(int i=1;i<=n;i++)cout<<query(1,1,n,i)<<' ';cout<<'\n';
}
return 0;
}