Framför Yuki ligger ett märkligt övergångsställe.

Detta övergångsställe kan betraktas som ett träd med $n$ noder. Den $i$-te kanten förbinder nod $u_i$ och nod $v_i$. Varje nod är färgad antingen svart eller vit, vilket beskrivs av en binär sträng $s$ av längd $n$:

• Om $s_i=0$ är färgen på nod $i$ svart.

• Om $s_i=1$ är färgen på nod $i$ vit.

Yuki har en hoppförmåga $k$, vilket innebär att när hon befinner sig vid nod $x$ kan hon hoppa till vilken nod $y$ som helst sådan att $\operatorname{dist}(x,y)\le k$. Här betecknar $\operatorname{dist}(x,y)$ antalet kanter på den enkla vägen mellan nod $x$ och nod $y$.

Härnäst kommer Yuki att utföra $n-1$ rundor av hoppande på övergångsstället. I den $i$-te rundan startar Yuki vid nod $1$ och vill nå nod $i+1$ genom en sekvens av hopp. Samtidigt vill Yuki minimera antalet gånger hon landar på en svart nod efter sina hopp.

Du behöver hjälpa Yuki att hitta det minsta antalet gånger hon landar på en svart nod för varje hopprunda.

Indata

Detta problem innehåller flera testfall.

Den första raden innehåller ett positivt heltal $t$ ($1\le t\le 10^5$), som representerar antalet testfall.

För varje testfall:

• Den första raden innehåller två positiva heltal $n,k$ ($1\le n\le 5\cdot 10^5$, $1\le k\le n$).

• Den andra raden innehåller en binär sträng $s$ av längd $n$ ($s_i\in\{0,1\}$).

• De följande $n-1$ raderna innehåller var och en två positiva heltal $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$).

Det garanteras att summan av $n$ över alla testfall inte överstiger $5\cdot 10^5$.

Utdata

För varje testfall, skriv ut en enda rad som innehåller $n-1$ heltal, där det $i$-te heltalet representerar det minsta antalet gånger Yuki landar på en svart nod under den $i$-te hopprundan.

Exempel

Exempelindata 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

Exempelutdata 1

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

Anmärkning

För det första testfallet:

• För den $1$:a hopprundan är en giltig sekvens av besökta noder $1,2$.

• För den $4$:e hopprundan är en giltig sekvens av besökta noder $1,3,5$.

För det andra testfallet:

• För den $4$:e hopprundan är en giltig sekvens av besökta noder $1,5$.

• För den $7$:e hopprundan är en giltig sekvens av besökta noder $1,5,8$.

• För den $8$:e hopprundan är en giltig sekvens av besökta noder $1,4,9$.