Vor Yuki liegt ein seltsamer Zebrastreifen.

Dieser Zebrastreifen kann als Baum mit $n$ Knoten betrachtet werden. Die $i$-te Kante verbindet Knoten $u_i$ und Knoten $v_i$. Jeder Knoten ist schwarz oder weiß gefärbt, beschrieben durch eine Binärzeichenkette $s$ der Länge $n$:

• Falls $s_i=0$, ist Knoten $i$ schwarz.

• Falls $s_i=1$, ist Knoten $i$ weiß.

Yuki hat eine Sprungfähigkeit $k$. Wenn sie sich bei Knoten $x$ befindet, kann sie also zu jedem Knoten $y$ mit $\operatorname{dist}(x,y)\le k$ springen. Dabei bezeichnet $\operatorname{dist}(x,y)$ die Anzahl der Kanten auf dem einfachen Pfad zwischen Knoten $x$ und Knoten $y$.

Als Nächstes absolviert Yuki $n-1$ Sprungrunden auf dem Zebrastreifen. In der $i$-ten Runde startet sie bei Knoten $1$ und möchte durch eine Folge von Sprüngen Knoten $i+1$ erreichen. Dabei möchte sie möglichst selten nach einem Sprung auf einem schwarzen Knoten landen.

Hilf Yuki, für jede Sprungrunde die minimale Anzahl von Landungen auf einem schwarzen Knoten zu bestimmen.

Eingabe

Diese Aufgabe enthält mehrere Testfälle.

Die erste Zeile enthält eine positive ganze Zahl $t$ ($1\le t\le 10^5$), die Anzahl der Testfälle.

Für jeden Testfall:

• Die erste Zeile enthält zwei positive ganze Zahlen $n,k$ ($1\le n\le 5\cdot 10^5$, $1\le k\le n$).

• Die zweite Zeile enthält eine Binärzeichenkette $s$ der Länge $n$ ($s_i\in\{0,1\}$).

• Die nächsten $n-1$ Zeilen enthalten jeweils zwei positive ganze Zahlen $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$).

Es ist garantiert, dass die Summe von $n$ über alle Testfälle höchstens $5\cdot 10^5$ beträgt.

Ausgabe

Gib für jeden Testfall eine Zeile mit $n-1$ ganzen Zahlen aus. Die $i$-te Zahl bezeichnet die minimale Anzahl von Landungen auf einem schwarzen Knoten während Yukis $i$-ter Sprungrunde.

Beispiele

Eingabe 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

Ausgabe 1

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

Hinweis

Für den ersten Testfall:

• In Sprungrunde $1$ ist $1,2$ eine mögliche Folge besuchter Knoten.

• In Sprungrunde $4$ ist $1,3,5$ eine mögliche Folge besuchter Knoten.

Für den zweiten Testfall:

• In Sprungrunde $4$ ist $1,5$ eine mögliche Folge besuchter Knoten.

• In Sprungrunde $7$ ist $1,5,8$ eine mögliche Folge besuchter Knoten.

• In Sprungrunde $8$ ist $1,4,9$ eine mögliche Folge besuchter Knoten.