Di depan Yuki terdapat sebuah zebra cross yang aneh.

Zebra cross ini dapat dipandang sebagai pohon dengan $n$ simpul. Sisi ke-$i$ menghubungkan simpul $u_i$ dan simpul $v_i$. Setiap simpul diwarnai hitam atau putih, yang dijelaskan oleh string biner $s$ sepanjang $n$:

• Jika $s_i=0$, simpul $i$ berwarna hitam.

• Jika $s_i=1$, simpul $i$ berwarna putih.

Yuki memiliki kemampuan melompat $k$, artinya ketika berada di simpul $x$, ia dapat melompat ke simpul $y$ mana pun yang memenuhi $\operatorname{dist}(x,y)\le k$. Di sini, $\operatorname{dist}(x,y)$ menyatakan jumlah sisi pada lintasan sederhana antara simpul $x$ dan simpul $y$.

Selanjutnya, Yuki akan melakukan $n-1$ ronde lompatan di zebra cross. Pada ronde ke-$i$, ia berangkat dari simpul $1$ dan ingin mencapai simpul $i+1$ melalui serangkaian lompatan. Pada saat yang sama, ia ingin meminimalkan jumlah pendaratan di simpul hitam setelah melompat.

Anda perlu membantu Yuki mencari jumlah minimum pendaratan di simpul hitam untuk setiap ronde lompatan.

Masukan

Soal ini memuat beberapa kasus uji.

Baris pertama berisi bilangan bulat positif $t$ ($1\le t\le 10^5$), yang menyatakan jumlah kasus uji.

Untuk setiap kasus uji:

• Baris pertama berisi dua bilangan bulat positif $n,k$ ($1\le n\le 5\cdot 10^5$, $1\le k\le n$).

• Baris kedua berisi string biner $s$ sepanjang $n$ ($s_i\in\{0,1\}$).

• Masing-masing dari $n-1$ baris berikutnya berisi dua bilangan bulat positif $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$).

Dijamin bahwa jumlah $n$ untuk semua kasus uji tidak melebihi $5\cdot 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris berisi $n-1$ bilangan bulat, dengan bilangan ke-$i$ menyatakan jumlah minimum pendaratan Yuki di simpul hitam selama ronde lompatan ke-$i$.

Contoh

Masukan 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

Keluaran 1

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

Catatan

Untuk kasus uji pertama:

• Pada ronde lompatan ke-$1$, salah satu urutan simpul yang dikunjungi yang valid adalah $1,2$.

• Pada ronde lompatan ke-$4$, salah satu urutan simpul yang dikunjungi yang valid adalah $1,3,5$.

Untuk kasus uji kedua:

• Pada ronde lompatan ke-$4$, salah satu urutan simpul yang dikunjungi yang valid adalah $1,5$.

• Pada ronde lompatan ke-$7$, salah satu urutan simpul yang dikunjungi yang valid adalah $1,5,8$.

• Pada ronde lompatan ke-$8$, salah satu urutan simpul yang dikunjungi yang valid adalah $1,4,9$.