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$ 輪，Yuki 由節點 $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$。

第二組測試資料：

• 第 $4$ 輪跳躍，一個合法嘅到訪節點序列係 $1,5$。

• 第 $7$ 輪跳躍，一個合法嘅到訪節點序列係 $1,5,8$。

• 第 $8$ 輪跳躍，一個合法嘅到訪節點序列係 $1,4,9$。