Перед Yuki розташований дивний пішохідний перехід.

Цей перехід можна розглядати як дерево з $n$ вершинами. $i$-те ребро з'єднує вершини $u_i$ та $v_i$. Кожна вершина пофарбована в чорний або білий колір, що описується двійковим рядком $s$ довжини $n$:

• Якщо $s_i=0$, вершина $i$ чорна.

• Якщо $s_i=1$, вершина $i$ біла.

Yuki має здатність до стрибків $k$: перебуваючи у вершині $x$, вона може стрибнути до будь-якої вершини $y$, для якої $\operatorname{dist}(x,y)\le k$. Тут $\operatorname{dist}(x,y)$ означає кількість ребер на простому шляху між вершинами $x$ та $y$.

Далі Yuki виконає $n-1$ раунд стрибків на переході. У $i$-му раунді вона починає у вершині $1$ і хоче дістатися вершини $i+1$ за допомогою послідовності стрибків. Водночас вона хоче мінімізувати кількість приземлень на чорну вершину після стрибків.

Допоможіть Yuki знайти найменшу кількість приземлень на чорну вершину для кожного раунду стрибків.

Вхідні дані

Задача містить кілька наборів вхідних даних.

Перший рядок містить додатне ціле число $t$ ($1\le t\le 10^5$) — кількість наборів вхідних даних.

Для кожного набору вхідних даних:

• Перший рядок містить два додатні цілі числа $n,k$ ($1\le n\le 5\cdot 10^5$, $1\le k\le n$).

• Другий рядок містить двійковий рядок $s$ довжини $n$ ($s_i\in\{0,1\}$).

• Кожен із наступних $n-1$ рядків містить два додатні цілі числа $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$).

Гарантується, що сума $n$ за всіма наборами вхідних даних не перевищує $5\cdot 10^5$.

Вихідні дані

Для кожного набору виведіть один рядок із $n-1$ цілих чисел, де $i$-те число означає найменшу кількість приземлень Yuki на чорну вершину в $i$-му раунді стрибків.

Приклади

Вхідні дані 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

Вихідні дані 1

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

Примітка

Для першого набору вхідних даних:

• У раунді стрибків $1$ одна з допустимих послідовностей відвіданих вершин — $1,2$.

• У раунді стрибків $4$ одна з допустимих послідовностей відвіданих вершин — $1,3,5$.

Для другого набору вхідних даних:

• У раунді стрибків $4$ одна з допустимих послідовностей відвіданих вершин — $1,5$.

• У раунді стрибків $7$ одна з допустимих послідовностей відвіданих вершин — $1,5,8$.

• У раунді стрибків $8$ одна з допустимих послідовностей відвіданих вершин — $1,4,9$.