Yuki の目の前には奇妙な横断歩道があります。

この横断歩道は $n$ 個の頂点を持つ木とみなせます。$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結びます。各頂点は黒または白に塗られており、長さ $n$ の二進文字列 $s$ で表されます。

• $s_i=0$ なら、頂点 $i$ は黒です。

• $s_i=1$ なら、頂点 $i$ は白です。

Yuki の跳躍能力は $k$ です。これは、頂点 $x$ にいるとき、$\operatorname{dist}(x,y)\le k$ を満たす任意の頂点 $y$ に跳べることを意味します。ここで、$\operatorname{dist}(x,y)$ は頂点 $x$ と頂点 $y$ を結ぶ単純パス上の辺の数です。

これから Yuki は横断歩道で $n-1$ ラウンドの跳躍を行います。$i$ 番目のラウンドでは頂点 $1$ から出発し、何回かの跳躍で頂点 $i+1$ に到達したいと考えています。同時に、跳躍後に黒い頂点に着地する回数を最小化したいと考えています。

各ラウンドについて、黒い頂点に着地する最小回数を求め、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\ne 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$ は有効です。

2 番目のテストケースについて：

• 第 $4$ ラウンドで訪れる頂点の列として、$1,5$ は有効です。

• 第 $7$ ラウンドで訪れる頂点の列として、$1,5,8$ は有効です。

• 第 $8$ ラウンドで訪れる頂点の列として、$1,4,9$ は有効です。