You are playing a VR game about adventures in an ancient world. You were on a journey to find the legendary treasure, and after breaking through several gates, you found a box that was supposed to contain the treasure. But the box had a lock on it with the following message: "To open the box, change the letters under the box well, so that it reads the same forward and backward."
After looking under the box, you found a string consisting of N characters in a row. The i-th character is located at position (i, 0), so distances between adjacent characters are 1.
It seems that the box can be opened by replacing the characters under the box and making it a palindrome. To do that, you start at some position, and you can repeatedly move to another position and replace the character at that position by any other character, until the string becomes a palindrome.
Since your HP is limited, you want to gain the treasure using minimum HP. Each position requires a different amount of HP to replace the respective character. Also, it consumes C HP to move a unit distance. That is, if you were at position (i, 0), and you want to move to position (j, 0) to replace the j-th character, the movement will decrease your HP by C·|j - i|.
For each integer i such that 1 ≤ i ≤ N, find the minimum HP consumed to obtain the treasure if you start at position (i, 0).
The first line contains an integer T, the number of test cases (1 ≤ T ≤ 100 000). The test cases follow.
The first line of each test case contains two integers: N, the number of characters under the box (1 ≤ N ≤ 1 000 000), and C, the amount of HP consumed when moving a unit distance (1 ≤ C ≤ 109).
The second line consists of N characters. It represents the string under the box. Each letter is an uppercase English letter.
The third line contains N integers. The i-th integer represents the HP consumed to replace the i-th character. Each of these integers is between 1 and 109.
The sum of N over all test cases does not exceed 1 000 000.
For each test case, print N integers on a single line. The i-th integer must be the minimum HP consumed when starting at position (i, 0).
2 5 1 ABCDE 7 1 4 5 1 5 1 ABCDA 7 1 4 5 1
6 5 6 6 5 2 1 2 3 4
For the first test case, when the starting position is (1, 0), one of the optimal ways is to first move to position (2, 0) and change "B" to "D", then move to position (5, 0) and change "E" to "A".
