Opening the Treasure Box

Apeach set out on a journey to find a legendary treasure. After breaking through several gates, he found a box that is presumed to hold the treasure. The box was locked, and an inscription on it read: "To open the box, change the letters below it so that they read the same forwards and backwards."

Near the box, Apeach found several stone tablets lined up in a row beneath it, each with a letter written on it. Many more letter tablets were scattered around the box. It seems the box opens when the tablets in the row are replaced so that they form a palindrome (a word, number, or sentence that reads the same forwards and backwards). Apeach has little stamina, so he wants to get the treasure while spending as little as possible. Replacing each tablet costs a different amount of stamina. Moving one position costs $c$ stamina. That is, if the previous position was tablet $i$ and he now replaces tablet $j$, the move costs $c \cdot |j - i|$ stamina. For each of the $N$ tablets, find the minimum stamina needed to get the treasure when starting from that tablet's position.

The first line contains the number of test cases $T$ ($1 \le T \le 100,000$).

Each test case is given in the following format.

The first line contains the number of tablets $N$ ($1 \le N \le 1,000,000$) and the stamina $c$ spent to move one position ($1 \le c \le 10^9$).

The second line contains a string of length $N$. The $i$-th character is the letter written on the $i$-th tablet. Each character is an uppercase English letter.

The third line contains $N$ integers. The $i$-th integer is the stamina spent to replace the $i$-th tablet. Each value is between 1 and $10^9$, inclusive.

The sum of $N$ over all test cases does not exceed 1,000,000.

For each test case, print on one line the minimum stamina Apeach must spend when starting from the position of each tablet, separated by spaces.