À frente de Yuki há uma passadeira estranha.

Esta passadeira pode ser vista como uma árvore com $n$ vértices. A $i$-ésima aresta liga o vértice $u_i$ ao vértice $v_i$. Cada vértice é pintado de preto ou branco, conforme uma cadeia binária $s$ de comprimento $n$:

• Se $s_i=0$, o vértice $i$ é preto.

• Se $s_i=1$, o vértice $i$ é branco.

Yuki tem uma capacidade de salto $k$, o que significa que, quando está no vértice $x$, pode saltar para qualquer vértice $y$ tal que $\operatorname{dist}(x,y)\le k$. Aqui, $\operatorname{dist}(x,y)$ representa o número de arestas no caminho simples entre os vértices $x$ e $y$.

Em seguida, Yuki fará $n-1$ rondas de saltos na passadeira. Na $i$-ésima ronda, começa no vértice $1$ e quer chegar ao vértice $i+1$ através de uma sequência de saltos. Ao mesmo tempo, quer minimizar o número de vezes que aterra num vértice preto após os saltos.

Deves ajudar Yuki a encontrar o número mínimo de vezes que aterra num vértice preto em cada ronda de saltos.

Entrada

Este problema contém vários casos de teste.

A primeira linha contém um inteiro positivo $t$ ($1\le t\le 10^5$), que representa o número de casos de teste.

Para cada caso de teste:

• A primeira linha contém dois inteiros positivos $n,k$ ($1\le n\le 5\cdot 10^5$, $1\le k\le n$).

• A segunda linha contém uma cadeia binária $s$ de comprimento $n$ ($s_i\in\{0,1\}$).

• Cada uma das $n-1$ linhas seguintes contém dois inteiros positivos $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$).

É garantido que a soma de $n$ em todos os casos de teste não excede $5\cdot 10^5$.

Saída

Para cada caso de teste, escreve uma linha com $n-1$ inteiros, em que o $i$-ésimo representa o número mínimo de vezes que Yuki aterra num vértice preto durante a $i$-ésima ronda de saltos.

Exemplos

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

Saída 1

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

Nota

Para o primeiro caso de teste:

• Na ronda $1$ de saltos, uma sequência válida de vértices visitados é $1,2$.

• Na ronda $4$ de saltos, uma sequência válida de vértices visitados é $1,3,5$.

Para o segundo caso de teste:

• Na ronda $4$ de saltos, uma sequência válida de vértices visitados é $1,5$.

• Na ronda $7$ de saltos, uma sequência válida de vértices visitados é $1,5,8$.

• Na ronda $8$ de saltos, uma sequência válida de vértices visitados é $1,4,9$.