Di fronte a Yuki c'è uno strano attraversamento pedonale.

Questo attraversamento pedonale può essere visto come un albero con $n$ nodi. L'$i$-esimo arco collega il nodo $u_i$ e il nodo $v_i$. Ogni nodo è colorato di nero o di bianco, descritto da una stringa binaria $s$ di lunghezza $n$:

• Se $s_i=0$, il colore del nodo $i$ è nero.

• Se $s_i=1$, il colore del nodo $i$ è bianco.

Yuki ha una capacità di salto $k$, il che significa che quando si trova nel nodo $x$, può saltare in qualsiasi nodo $y$ tale che $\operatorname{dist}(x,y)\le k$. Qui, $\operatorname{dist}(x,y)$ indica il numero di archi sul cammino semplice tra il nodo $x$ e il nodo $y$.

Successivamente, Yuki effettuerà $n-1$ turni di salti sull'attraversamento pedonale. Nell'$i$-esimo turno, Yuki parte dal nodo $1$ e vuole raggiungere il nodo $i+1$ attraverso una sequenza di salti. Allo stesso tempo, Yuki vuole ridurre al minimo il numero di volte in cui atterra su un nodo nero dopo i suoi salti.

Devi aiutare Yuki a trovare il numero minimo di volte in cui atterra su un nodo nero per ciascun turno di salti.

Input

Questo problema contiene più casi di test.

La prima riga contiene un intero positivo $t$ ($1\le t\le 10^5$), che rappresenta il numero di casi di test.

Per ogni caso di test:

• La prima riga contiene due interi positivi $n,k$ ($1\le n\le 5\cdot 10^5$, $1\le k\le n$).

• La seconda riga contiene una stringa binaria $s$ di lunghezza $n$ ($s_i\in\{0,1\}$).

• Le successive $n-1$ righe contengono ciascuna due interi positivi $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$).

È garantito che la somma di $n$ su tutti i casi di test non superi $5\cdot 10^5$.

Output

Per ogni caso di test, stampa una singola riga contenente $n-1$ interi, dove l'$i$-esimo intero rappresenta il numero minimo di volte in cui Yuki atterra su un nodo nero durante l'$i$-esimo turno di salti.

Esempio

Input di esempio 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

Output di esempio 1

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

Nota

Per il primo caso di test:

• Per il $1$^o turno di salti, una sequenza valida di nodi visitati è $1,2$.

• Per il $4$^o turno di salti, una sequenza valida di nodi visitati è $1,3,5$.

Per il secondo caso di test:

• Per il $4$^o turno di salti, una sequenza valida di nodi visitati è $1,5$.

• Per il $7$^o turno di salti, una sequenza valida di nodi visitati è $1,5,8$.

• Per l'$8$^o turno di salti, una sequenza valida di nodi visitati è $1,4,9$.