Yuki 面前有一条奇怪的斑马线。

这条斑马线可以看作一棵拥有 $n$ 个节点的树。第 $i$ 条边连接节点 $u_i$ 和节点 $v_i$。

每个节点都被染成黑色或白色，由一个长度为 $n$ 的二进制字符串 $s$ 描述：

• 如果 $s_i = 0$，节点 $i$ 的颜色为黑色。
• 如果 $s_i = 1$，节点 $i$ 的颜色为白色。

Yuki 拥有跳跃能力 $k$，这意味着当她位于节点 $x$ 时，她可以跳跃到满足 $\text{dist}(x, y) \le k$ 的任意节点 $y$。这里，$\text{dist}(x, y)$ 表示节点 $x$ 和节点 $y$ 之间简单路径上的边数。

接下来，Yuki 将在斑马线上进行 $n - 1$ 轮跳跃。在第 $i$ 轮中，Yuki 从节点 $1$ 出发，希望通过一系列跳跃到达节点 $i + 1$。同时，Yuki 希望最小化跳跃后落在黑色节点上的次数。

你需要帮助 Yuki 求出每一轮跳跃中，她落在黑色节点上的最少次数。

输入格式

本题包含多个测试用例。

第一行包含一个正整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。

对于每个测试用例：

• 第一行包含两个正整数 $n, k$ ($1 \le n \le 5 \cdot 10^5$, $1 \le k \le n$)。
• 第二行包含一个长度为 $n$ 的二进制字符串 $s$ ($s_i \in \{0, 1\}$)。
• 接下来的 $n - 1$ 行，每行包含两个正整数 $u_i, v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$)。

保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行，包含 $n - 1$ 个整数，其中第 $i$ 个整数表示 Yuki 在第 $i$ 轮跳跃中落在黑色节点上的最少次数。

样例

输入样例 1

2
5 1
01010
3 5
2 1
1 3
3 4
9 3
100010000
1 2
2 3
2 4
3 5
3 6
4 7
6 8
7 9

输出样例 1

0 1 1 2
1 1 1 0 1 1 1 2

说明

对于第一个测试用例：

• 对于第 1 轮跳跃，一条有效的访问节点序列为 1, 2。
• 对于第 4 轮跳跃，一条有效的访问节点序列为 1, 3, 5。

对于第二个测试用例：

• 对于第 4 轮跳跃，一条有效的访问节点序列为 1, 5。
• 对于第 7 轮跳跃，一条有效的访问节点序列为 1, 5, 8。
• 对于第 8 轮跳跃，一条有效的访问节点序列为 1, 4, 9。