Trước mặt Yuki là một vạch sang đường kỳ lạ.

Vạch sang đường này có thể được xem là một cây có $n$ đỉnh. Cạnh thứ $i$ nối đỉnh $u_i$ với đỉnh $v_i$. Mỗi đỉnh được tô màu đen hoặc trắng, được mô tả bởi một xâu nhị phân $s$ có độ dài $n$:

• Nếu $s_i=0$, đỉnh $i$ có màu đen.

• Nếu $s_i=1$, đỉnh $i$ có màu trắng.

Yuki có khả năng nhảy $k$, nghĩa là khi ở đỉnh $x$, cô có thể nhảy đến bất kỳ đỉnh $y$ nào thỏa mãn $\operatorname{dist}(x,y)\le k$. Ở đây, $\operatorname{dist}(x,y)$ là số cạnh trên đường đi đơn giữa đỉnh $x$ và đỉnh $y$.

Tiếp theo, Yuki sẽ thực hiện $n-1$ lượt nhảy trên vạch sang đường. Trong lượt thứ $i$, cô bắt đầu từ đỉnh $1$ và muốn đến đỉnh $i+1$ bằng một chuỗi bước nhảy. Đồng thời, cô muốn giảm thiểu số lần đáp xuống đỉnh màu đen sau các bước nhảy.

Bạn cần giúp Yuki tìm số lần đáp xuống đỉnh màu đen ít nhất trong mỗi lượt nhảy.

Dữ liệu vào

Bài toán này có nhiều bộ test.

Dòng đầu tiên chứa một số nguyên dương $t$ ($1\le t\le 10^5$), là số bộ test.

Với mỗi bộ test:

• Dòng đầu tiên chứa hai số nguyên dương $n,k$ ($1\le n\le 5\cdot 10^5$, $1\le k\le n$).

• Dòng thứ hai chứa xâu nhị phân $s$ có độ dài $n$ ($s_i\in\{0,1\}$).

• Mỗi dòng trong $n-1$ dòng tiếp theo chứa hai số nguyên dương $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$).

Đảm bảo tổng $n$ trên tất cả các bộ test không vượt quá $5\cdot 10^5$.

Dữ liệu ra

Với mỗi bộ test, in một dòng gồm $n-1$ số nguyên, trong đó số thứ $i$ là số lần ít nhất Yuki đáp xuống đỉnh màu đen trong lượt nhảy thứ $i$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

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

Ghi chú

Với bộ test thứ nhất:

• Trong lượt nhảy thứ $1$, một dãy đỉnh được ghé thăm hợp lệ là $1,2$.

• Trong lượt nhảy thứ $4$, một dãy đỉnh được ghé thăm hợp lệ là $1,3,5$.

Với bộ test thứ hai:

• Trong lượt nhảy thứ $4$, một dãy đỉnh được ghé thăm hợp lệ là $1,5$.

• Trong lượt nhảy thứ $7$, một dãy đỉnh được ghé thăm hợp lệ là $1,5,8$.

• Trong lượt nhảy thứ $8$, một dãy đỉnh được ghé thăm hợp lệ là $1,4,9$.