Devant Yuki se trouve un étrange passage piéton.

Ce passage piéton peut être vu comme un arbre à $n$ sommets. La $i$-ème arête relie les sommets $u_i$ et $v_i$. Chaque sommet est colorié en noir ou en blanc, ce que décrit une chaîne binaire $s$ de longueur $n$ :

• Si $s_i=0$, le sommet $i$ est noir.

• Si $s_i=1$, le sommet $i$ est blanc.

Yuki possède une capacité de saut $k$, ce qui signifie que, lorsqu'elle se trouve au sommet $x$, elle peut sauter vers n'importe quel sommet $y$ tel que $\operatorname{dist}(x,y)\le k$. Ici, $\operatorname{dist}(x,y)$ désigne le nombre d'arêtes du chemin simple entre les sommets $x$ et $y$.

Yuki effectuera ensuite $n-1$ manches de sauts sur le passage piéton. Lors de la $i$-ème manche, elle part du sommet $1$ et souhaite atteindre le sommet $i+1$ par une suite de sauts. Elle souhaite en même temps minimiser le nombre de fois où elle atterrit sur un sommet noir après ses sauts.

Vous devez aider Yuki à déterminer le nombre minimal d'atterrissages sur un sommet noir pour chaque manche de sauts.

Entrée

Ce problème contient plusieurs cas de test.

La première ligne contient un entier positif $t$ ($1\le t\le 10^5$), le nombre de cas de test.

Pour chaque cas de test :

• La première ligne contient deux entiers positifs $n,k$ ($1\le n\le 5\cdot 10^5$, $1\le k\le n$).

• La deuxième ligne contient une chaîne binaire $s$ de longueur $n$ ($s_i\in\{0,1\}$).

• Chacune des $n-1$ lignes suivantes contient deux entiers positifs $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$).

Il est garanti que la somme des $n$ sur tous les cas de test ne dépasse pas $5\cdot 10^5$.

Sortie

Pour chaque cas de test, affichez une ligne contenant $n-1$ entiers ; le $i$-ème représente le nombre minimal de fois où Yuki atterrit sur un sommet noir pendant la $i$-ème manche de sauts.

Exemples

Entrée 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

Sortie 1

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

Remarque

Pour le premier cas de test :

• Lors de la manche $1$, une suite valide de sommets visités est $1,2$.

• Lors de la manche $4$, une suite valide de sommets visités est $1,3,5$.

Pour le deuxième cas de test :

• Lors de la manche $4$, une suite valide de sommets visités est $1,5$.

• Lors de la manche $7$, une suite valide de sommets visités est $1,5,8$.

• Lors de la manche $8$, une suite valide de sommets visités est $1,4,9$.