Yuki의 앞에는 이상한 횡단보도가 있습니다.

이 횡단보도는 $n$개의 정점으로 이루어진 트리로 볼 수 있습니다. $i$번째 간선은 정점 $u_i$와 정점 $v_i$를 연결합니다. 각 정점은 검은색 또는 흰색으로 칠해져 있으며, 이는 길이 $n$인 이진 문자열 $s$로 설명됩니다:

• $s_i=0$이면 정점 $i$의 색깔은 검은색입니다.

• $s_i=1$이면 정점 $i$의 색깔은 흰색입니다.

Yuki의 점프 능력은 $k$이며, 이는 그녀가 정점 $x$에 있을 때 $\operatorname{dist}(x,y)\le k$를 만족하는 임의의 정점 $y$로 점프할 수 있음을 의미합니다. 여기서 $\operatorname{dist}(x,y)$는 정점 $x$와 정점 $y$ 사이의 단순 경로 위에 있는 간선의 개수를 나타냅니다.

다음으로 Yuki는 횡단보도에서 $n-1$번의 점프 라운드를 수행할 것입니다. $i$번째 라운드에서 Yuki는 정점 $1$에서 출발하여 일련의 점프를 통해 정점 $i+1$에 도달하려고 합니다. 동시에 Yuki는 점프 후에 검은색 정점에 착지하는 횟수를 최소화하고 싶어 합니다.

각 점프 라운드마다 Yuki가 검은색 정점에 착지하는 최소 횟수를 구하는 것을 도와주세요.

입력

이 문제는 여러 개의 테스트 케이스를 포함합니다.

첫 번째 줄에는 테스트 케이스의 수를 나타내는 양의 정수 $t$ ($1\le t\le 10^5$)가 주어집니다.

각 테스트 케이스에 대해:

• 첫 번째 줄에는 두 개의 양의 정수 $n,k$ ($1\le n\le 5\cdot 10^5$, $1\le k\le n$)가 주어집니다.

• 두 번째 줄에는 길이 $n$인 이진 문자열 $s$ ($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$번째 정수는 $i$번째 점프 라운드 동안 Yuki가 검은색 정점에 착지하는 최소 횟수를 나타냅니다.

예제

예제 입력 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$입니다.