Foran Yuki er det et merkelig fotgjengerfelt.

Dette fotgjengerfeltet kan betraktes som et tre med $n$ noder. Den $i$-te kanten forbinder node $u_i$ og node $v_i$. Hver node er farget enten svart eller hvit, beskrevet av en binær streng $s$ med lengde $n$:

• Hvis $s_i=0$, er fargen på node $i$ svart.

• Hvis $s_i=1$, er fargen på node $i$ hvit.

Yuki har en hoppeevne $k$, noe som betyr at når hun er i node $x$, kan hun hoppe til en hvilken som helst node $y$ slik at $\operatorname{dist}(x,y)\le k$. Her betegner $\operatorname{dist}(x,y)$ antallet kanter på den enkle stien mellom node $x$ og node $y$.

Deretter vil Yuki utføre $n-1$ runder med hopping på fotgjengerfeltet. I den $i$-te runden starter Yuki i node $1$ og ønsker å nå node $i+1$ gjennom en sekvens av hopp. Samtidig ønsker Yuki å minimere antallet ganger hun lander på en svart node etter hoppene sine.

Du må hjelpe Yuki med å finne det minste antallet ganger hun lander på en svart node for hver runde med hopping.

Inndata

Dette problemet inneholder flere testtilfeller.

Den første linjen inneholder et positivt heltall $t$ ($1\le t\le 10^5$), som representerer antallet testtilfeller.

For hvert testtilfelle:

• Den første linjen inneholder to positive heltall $n,k$ ($1\le n\le 5\cdot 10^5$, $1\le k\le n$).

• Den andre linjen inneholder en binær streng $s$ med lengde $n$ ($s_i\in\{0,1\}$).

• De neste $n-1$ linjene inneholder hver to positive heltall $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$).

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $5\cdot 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut én enkelt linje som inneholder $n-1$ heltall, der det $i$-te heltallet representerer det minste antallet ganger Yuki lander på en svart node under den $i$-te runden med hopping.

Eksempel

Eksempelinndata 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

Eksempelutdata 1

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

Merk

For det første testtilfellet:

• For den $1$. runden med hopping er én gyldig sekvens av besøkte noder $1,2$.

• For den $4$. runden med hopping er én gyldig sekvens av besøkte noder $1,3,5$.

For det andre testtilfellet:

• For den $4$. runden med hopping er én gyldig sekvens av besøkte noder $1,5$.

• For den $7$. runden med hopping er én gyldig sekvens av besøkte noder $1,5,8$.

• For den $8$. runden med hopping er én gyldig sekvens av besøkte noder $1,4,9$.