In front of Yuki is a strange zebra crossing.

This zebra crossing can be viewed as a tree with $n$ nodes. The $i$-th edge connects node $u_i$ and node $v_i$. Each node is colored either black or white, described by a binary string $s$ of length $n$:

• If $s_i=0$, the color of node $i$ is black.

• If $s_i=1$, the color of node $i$ is white.

Yuki has a jumping ability $k$, which means that when she is at node $x$, she can jump to any node $y$ such that $\operatorname{dist}(x,y)\le k$. Here, $\operatorname{dist}(x,y)$ denotes the number of edges on the simple path between node $x$ and node $y$.

Next, Yuki will perform $n-1$ rounds of jumping on the zebra crossing. In the $i$-th round, Yuki starts at node $1$ and wants to reach node $i+1$ through a sequence of jumps. At the same time, Yuki wants to minimize the number of times she lands on a black node after her jumps.

You need to help Yuki find the minimum number of times she lands on a black node for each round of jumping.

Input

This problem contains multiple test cases.

The first line contains a positive integer $t$ ($1\le t\le 10^5$), representing the number of test cases.

For each test case:

• The first line contains two positive integers $n,k$ ($1\le n\le 5\cdot 10^5$, $1\le k\le n$).

• The second line contains a binary string $s$ of length $n$ ($s_i\in\{0,1\}$).

• The next $n-1$ lines each contain two positive integers $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5\cdot 10^5$.

Output

For each test case, output a single line containing $n-1$ integers, where the $i$-th integer represents the minimum number of times Yuki lands on a black node during the $i$-th round of jumping.

Examples

Input 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

Output 1

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

Note

For the first test case:

• For the $1$-st round of jumping, one valid sequence of visited nodes is $1,2$.

• For the $4$-th round of jumping, one valid sequence of visited nodes is $1,3,5$.

For the second test case:

• For the $4$-th round of jumping, one valid sequence of visited nodes is $1,5$.

• For the $7$-th round of jumping, one valid sequence of visited nodes is $1,5,8$.

• For the $8$-th round of jumping, one valid sequence of visited nodes is $1,4,9$.