你在玩一款关于古代世界冒险的 VR 游戏。你在寻找传说中的宝藏，在突破了几道关卡后，你发现了一个本应装有宝藏的盒子。但盒子上有一把锁，上面写着：“要打开盒子，请修改盒子下方的字母，使其正读反读都一样。”

检查盒子下方后，你发现了一串由 $N$ 个字符组成的字符串。第 $i$ 个字符位于位置 $(i, 0)$，因此相邻字符之间的距离为 1。

看来，可以通过替换盒子下方的字符并将其变为回文串来打开盒子。为此，你从某个位置开始，可以反复移动到另一个位置，并将该位置的字符替换为任何其他字符，直到字符串变成回文串。

由于你的 HP 有限，你希望以最小的 HP 消耗获得宝藏。每个位置替换相应字符所需的 HP 不同。此外，移动单位距离会消耗 $C$ 点 HP。也就是说，如果你在位置 $(i, 0)$，想要移动到位置 $(j, 0)$ 替换第 $j$ 个字符，移动将消耗 $C \cdot |j - i|$ 点 HP。

对于每个满足 $1 \le i \le N$ 的整数 $i$，求出从位置 $(i, 0)$ 开始获得宝藏所需的最小 HP 消耗。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量 ($1 \le T \le 100\,000$)。接下来是各测试用例。 每个测试用例的第一行包含两个整数：$N$，盒子下方的字符数量 ($1 \le N \le 1\,000\,000$)，以及 $C$，移动单位距离消耗的 HP ($1 \le C \le 10^9$)。 第二行包含 $N$ 个字符，表示盒子下方的字符串。每个字母都是大写英文字母。 第三行包含 $N$ 个整数，第 $i$ 个整数表示替换第 $i$ 个字符所需的 HP。这些整数均在 $1$ 到 $10^9$ 之间。 所有测试用例的 $N$ 之和不超过 $1\,000\,000$。

输出格式

对于每个测试用例，在一行中打印 $N$ 个整数。第 $i$ 个整数表示从位置 $(i, 0)$ 开始时的最小 HP 消耗。

样例

样例输入 1

2
5 1
ABCDE
7 1 4 5 1
5 1
ABCDA
7 1 4 5 1

样例输出 1

6 5 6 6 5
2 1 2 3 4

说明

对于第一个测试用例，当起始位置为 $(1, 0)$ 时，一种最优方案是先移动到位置 $(2, 0)$ 并将 “B” 改为 “D”，然后移动到位置 $(5, 0)$ 并将 “E” 改为 “A”。