Frente a Yuki hay un extraño paso de cebra.

Este paso de cebra puede verse como un árbol con $n$ nodos. La $i$-ésima arista conecta el nodo $u_i$ con el nodo $v_i$. Cada nodo está pintado de negro o blanco, según una cadena binaria $s$ de longitud $n$:

• Si $s_i=0$, el nodo $i$ es negro.

• Si $s_i=1$, el nodo $i$ es blanco.

Yuki tiene una capacidad de salto $k$, lo que significa que, cuando está en el nodo $x$, puede saltar a cualquier nodo $y$ tal que $\operatorname{dist}(x,y)\le k$. Aquí, $\operatorname{dist}(x,y)$ denota el número de aristas del camino simple entre el nodo $x$ y el nodo $y$.

A continuación, Yuki realizará $n-1$ rondas de saltos sobre el paso de cebra. En la $i$-ésima ronda, parte del nodo $1$ y quiere llegar al nodo $i+1$ mediante una secuencia de saltos. Al mismo tiempo, quiere minimizar el número de veces que aterriza en un nodo negro tras sus saltos.

Debes ayudar a Yuki a hallar el mínimo número de veces que aterriza en un nodo negro en cada ronda de saltos.

Entrada

Este problema contiene múltiples casos de prueba.

La primera línea contiene un entero positivo $t$ ($1\le t\le 10^5$), que representa el número de casos de prueba.

Para cada caso de prueba:

• La primera línea contiene dos enteros positivos $n,k$ ($1\le n\le 5\cdot 10^5$, $1\le k\le n$).

• La segunda línea contiene una cadena binaria $s$ de longitud $n$ ($s_i\in\{0,1\}$).

• Cada una de las siguientes $n-1$ líneas contiene dos enteros positivos $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$).

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $5\cdot 10^5$.

Salida

Para cada caso de prueba, imprime una línea con $n-1$ enteros, donde el $i$-ésimo entero representa el mínimo número de veces que Yuki aterriza en un nodo negro durante la $i$-ésima ronda de saltos.

Ejemplos

Entrada 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

Salida 1

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

Nota

Para el primer caso de prueba:

• En la ronda $1$ de saltos, una secuencia válida de nodos visitados es $1,2$.

• En la ronda $4$ de saltos, una secuencia válida de nodos visitados es $1,3,5$.

Para el segundo caso de prueba:

• En la ronda $4$ de saltos, una secuencia válida de nodos visitados es $1,5$.

• En la ronda $7$ de saltos, una secuencia válida de nodos visitados es $1,5,8$.

• En la ronda $8$ de saltos, una secuencia válida de nodos visitados es $1,4,9$.