Przed Yuki znajduje się dziwne przejście dla pieszych.

Można je traktować jako drzewo o $n$ wierzchołkach. $i$-ta krawędź łączy wierzchołki $u_i$ i $v_i$. Każdy wierzchołek jest czarny albo biały, co opisuje ciąg binarny $s$ długości $n$:

• Jeśli $s_i=0$, wierzchołek $i$ jest czarny.

• Jeśli $s_i=1$, wierzchołek $i$ jest biały.

Yuki ma zdolność skakania $k$: będąc w wierzchołku $x$, może skoczyć do dowolnego wierzchołka $y$ takiego, że $\operatorname{dist}(x,y)\le k$. Tutaj $\operatorname{dist}(x,y)$ oznacza liczbę krawędzi na ścieżce prostej między wierzchołkami $x$ i $y$.

Następnie Yuki wykona $n-1$ rund skoków na przejściu. W $i$-tej rundzie zaczyna w wierzchołku $1$ i chce dotrzeć do wierzchołka $i+1$ za pomocą ciągu skoków. Jednocześnie chce zminimalizować liczbę lądowań na czarnym wierzchołku po skokach.

Pomóż Yuki znaleźć minimalną liczbę lądowań na czarnym wierzchołku w każdej rundzie skoków.

Wejście

Zadanie zawiera wiele przypadków testowych.

Pierwszy wiersz zawiera dodatnią liczbę całkowitą $t$ ($1\le t\le 10^5$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego:

• Pierwszy wiersz zawiera dwie dodatnie liczby całkowite $n,k$ ($1\le n\le 5\cdot 10^5$, $1\le k\le n$).

• Drugi wiersz zawiera ciąg binarny $s$ długości $n$ ($s_i\in\{0,1\}$).

• Każdy z kolejnych $n-1$ wierszy zawiera dwie dodatnie liczby całkowite $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$).

Zagwarantowano, że suma $n$ we wszystkich przypadkach testowych nie przekracza $5\cdot 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający $n-1$ liczb całkowitych. $i$-ta liczba oznacza minimalną liczbę lądowań Yuki na czarnym wierzchołku w $i$-tej rundzie skoków.

Przykład

Wejście 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

Wyjście 1

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

Uwagi

Dla pierwszego przypadku testowego:

• W $1$-szej rundzie skoków jednym z poprawnych ciągów odwiedzonych wierzchołków jest $1,2$.

• W $4$-tej rundzie skoków jednym z poprawnych ciągów odwiedzonych wierzchołków jest $1,3,5$.

Dla drugiego przypadku testowego:

• W $4$-tej rundzie skoków jednym z poprawnych ciągów odwiedzonych wierzchołków jest $1,5$.

• W $7$-mej rundzie skoków jednym z poprawnych ciągów odwiedzonych wierzchołków jest $1,5,8$.

• W $8$-mej rundzie skoków jednym z poprawnych ciągów odwiedzonych wierzchołków jest $1,4,9$.