Yukin edessä on outo suojatie.

Tätä suojatietä voidaan tarkastella puuna, jossa on $n$ solmua. $i$:s kaari yhdistää solmun $u_i$ ja solmun $v_i$. Jokainen solmu on väritetty joko mustaksi tai valkoiseksi, mikä kuvataan pituutta $n$ olevalla binäärimerkkijonolla $s$:

• Jos $s_i=0$, solmun $i$ väri on musta.

• Jos $s_i=1$, solmun $i$ väri on valkoinen.

Yukilla on hyppykyky $k$, mikä tarkoittaa, että ollessaan solmussa $x$ hän voi hypätä mihin tahansa solmuun $y$, jolle pätee $\operatorname{dist}(x,y)\le k$. Tässä $\operatorname{dist}(x,y)$ tarkoittaa kaarien lukumäärää yksinkertaisella polulla solmun $x$ ja solmun $y$ välillä.

Seuraavaksi Yuki suorittaa $n-1$ hyppelykierrosta suojatiellä. Kierroksella $i$ Yuki aloittaa solmusta $1$ ja haluaa päästä solmuun $i+1$ hyppyjen sarjalla. Samalla Yuki haluaa minimoida niiden kertojen lukumäärän, jolloin hän laskeutuu mustaan solmuun hyppyjensä jälkeen.

Sinun tulee auttaa Yukia löytämään pienin mahdollinen mustaan solmuun laskeutumisten lukumäärä jokaiselle hyppelykierrokselle.

Syöte

Tämä tehtävä sisältää useita testitapauksia.

Ensimmäinen rivi sisältää positiivisen kokonaisluvun $t$ ($1\le t\le 10^5$), joka kuvaa testitapausten lukumäärää.

Jokaiselle testitapaukselle:

• Ensimmäinen rivi sisältää kaksi positiivista kokonaislukua $n,k$ ($1\le n\le 5\cdot 10^5$, $1\le k\le n$).

• Toinen rivi sisältää pituutta $n$ olevan binäärimerkkijonon $s$ ($s_i\in\{0,1\}$).

• Seuraavat $n-1$ riviä sisältävät kukin kaksi positiivista kokonaislukua $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$).

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $5\cdot 10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi rivi, joka sisältää $n-1$ kokonaislukua, missä $i$:s kokonaisluku kuvaa pienintä määrää kertoja, jolloin Yuki laskeutuu mustaan solmuun $i$:nnen hyppelykierroksen aikana.

Esimerkki

Esimerkkisyöte 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

Esimerkkituloste 1

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

Huomautus

Ensimmäisessä testitapauksessa:

• $1$. hyppelykierroksella yksi kelvollinen vierailtujen solmujen jono on $1,2$.

• $4$. hyppelykierroksella yksi kelvollinen vierailtujen solmujen jono on $1,3,5$.

Toisessa testitapauksessa:

• $4$. hyppelykierroksella yksi kelvollinen vierailtujen solmujen jono on $1,5$.

• $7$. hyppelykierroksella yksi kelvollinen vierailtujen solmujen jono on $1,5,8$.

• $8$. hyppelykierroksella yksi kelvollinen vierailtujen solmujen jono on $1,4,9$.