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$。