Перед 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$.